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

学术版

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 LionBlaze @ 2024-11-28 18:34:48

@Z_301 怎么生成每个数不相同的序列啊 qwq

by djfuck @ 2024-11-28 18:35:07

我们设长度为 N, 值域为 M 的单调不降序列有 S 个.

能否考虑将一个 [1, S] 的整数和一个单调不降序列一一对应, 从而转化为生成一个 [1, S] 的整数再映射回去?

by LionBlaze @ 2024-11-28 18:36:02

@djfuck 我也这么想过可是我这个蒟蒻居然不知道怎么求 S。

如果能构造这样的映射肯定就可以了。

by Z_301 @ 2024-11-28 18:37:06

@LionBlaze 如果 M=O(N) ，那么可以直接 shuffle [1,M]，否则每次随一个直到没有出现，这样期望是 O(N) 的。

by djfuck @ 2024-11-28 18:37:07

可能要推一下式子?

我先去 oeis 上面搜一下看看(

by LionBlaze @ 2024-11-28 18:37:41

求 S 可以动规。但是动规出来的性质能好吗？

by Z_301 @ 2024-11-28 18:38:58

然后根据我讲的那个随机方法，S=\binom{N+M-1}{N} ，其实就是插板法。

by djfuck @ 2024-11-28 18:39:32

哦不对就算你能 O(n) 算出来 S 那也没用, 因为从一个整数反推一个序列需要其他的值

by LionBlaze @ 2024-11-28 18:40:12

@Z_301 没有出现是什么意思 qwq，另外在“更进一步”里面没有 M（不过只解决基础版也可以，肯定会关注）

by LionBlaze @ 2024-11-28 18:41:31

@Z_301 插板法？但是要保证单调不降啊