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.
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.
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.