Sample a random non-decreasing sequence 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.
Python, 89 bytes



from random import*
lambda n,k:[x-i for i,x in enumerate(sorted(sample(range(1,n+k),k)))]


Generating an increasing sequence rather than a non-decreasing one would be straightforward: this is just a random subset of k numbers between 1 and n, sorted.

But, we can convert an increasing sequence to a non-decreasing one by shrinking each gap between consecutive numbers by 1. So, a gap of 1 becomes a gap of 0, making equal numbers. To do so, decrease the i'th largest value by i

r[0], r[1], ..., r[n-1]  =&gt;  r[0]-0, r[1]-1, ..., r[n-1]-(n-1)


For the result to be from 1 to n, the input must be from 1 to n+k-1. This gives a bijection between non-decreasing sequences of numbers between 1 and n, to increasing sequences between 1 and n+k-1. The same bijection is used in the stars and bars argument for counting such sequences.

The code uses the python function random.sample, which takes k samples without replacement from the input list. Sorting it gives the increasing sequence.