20
1
Input: Two integers n and k given in any form that is convenient for your code
Output A random non-decreasing sequence of k integers, each in the range 1 to n. The sample should be chosen uniformly from all non-decreasing sequences of k integers with integers in the range 1 to n.
The output can be in any reasonable format you find convenient.
You can use whatever pseudo-random generator your favorite library/language provides.
We can assume that the integers n,k > 0.
Example
Say n,k = 2. The non-decreasing sequences are
1,1
1,2
2,2
Each sequence should have probability 1/3 of being outputted.
Restriction
Your code should run in no more than a few seconds for k = 20 and n = 100.
What doesn't work
If you just sample each integer randomly from the range 1 to n and then sort the list you won't get a uniform distribution.
Outputting the number of non-decreasing sequences for n,k might make an interesting challenge on its own, if it hasn't already been done... – ETHproductions – 2016-11-17T16:35:39.453
1
@ETHproductions Not really, it's just a binomial (related to this)
– Sp3000 – 2016-11-17T16:49:19.240@Sp3000 Ah, OK. It was a fun challenge for me to figure out how to calculate it efficiently though. – ETHproductions – 2016-11-17T16:53:06.873
Your requirement that each sequence have equal probability of being output is not possible to satisfy with most garden variety PRNGs which may have just 32 or 48 bit states. According to Wolfram, there are 535 quintillion 20 element subsequences of 1, ..., 100 (didn't check how many of them are nondecreasing). 2^64 is just 18 quintillion. – Sinan Ünür – 2016-11-18T16:03:09.937