如何均匀随机地产生一个单调不降序列

rt。

问题：

给定 $N,M$，如何真正均匀随机（指每种可能的序列的概率相同）出一个长度为 $N$ 的单调不降序列（所以可以有相同的），每个元素是在 $[1,M]$ 中的整数。

显然生成所有数字再排序不是正确的，当 $N=2$ 时就有：

容易验证概率和为 $M \times \dfrac{1}{M^2} + M(M-1) \times \dfrac{1}{M^2} = 1$。

更进一步地，如果我们有一个能够均匀随机地产生某种类型（比如一个类）的随机对象产生器，同时有这种类型的小于号重载（可以比较两个对象，并且性质良好），还有这种类型的等于号重载，给定 $N$，如何产生一个长度为 $N$ 的，对于每个 $1 \le i < j \le N$ 都有 $a_i \le a_j$（这里的 $\le$ 表示重载后的 a<b || a==b）的序列 $a_{1 \cdots N}$。

解答必关。