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

学术版

LionBlaze @ 2024-11-28 18:09:35

rt。

问题：

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

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

如果两个数字 x,y 相同，则概率为 \dfrac{1}{M^2}。
如果两个数字 x,y（这是经过排序的生成的序列，满足 x < y）不同，概率为 \dfrac{2}{M^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}。

解答必关。

by yukimianyan @ 2024-11-28 18:41:56

@Z_301 随机的艺术选择一节的方法是不是更好，这样就一定没有重复了。

by LionBlaze @ 2024-11-28 18:42:14

哦是我唐了，这个每一个板是表示板子前面的数量不是到上一个板的距离

by PosVII @ 2024-11-28 18:42:43

@LionBlaze 插板法不就保证了单调不降吗

by LionBlaze @ 2024-11-28 18:44:10

@PosVII 我原本学的插板法是

O|OO|O||OOOO

表示 1,2,1,0,4

这里的应该是前缀和对吧

by djfuck @ 2024-11-28 18:47:10

那能不能这样:

我们设 f(N, M) = \binom{N+M-1}{N}, x 是 [1, S] 中的一个随机数.

然后一位一位的生成序列, 每一次只要找一个最小的 u 使得 x > \sum^{u-1}_{i=1} f(i, len-1).

找到这样的 u 之后 len \leftarrow len - 1, u \leftarrow u - \sum^{u-1}_{i=1} f(i, len-1), 然后循环往复.

by djfuck @ 2024-11-28 18:48:13

@djfuck 我先写一下试试

by LionBlaze @ 2024-11-28 18:48:49

@djfuck 啊？这是什么原理

by LionBlaze @ 2024-11-28 18:54:55

首先肯定是均匀随机的。

然后原理大概懂了

by LionBlaze @ 2024-11-28 19:01:08

但是这样的序列为什么是单调不降的

by djfuck @ 2024-11-28 19:02:22

等一下我看我能不能直接搞出来一个 code