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

学术版

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:10:13

百度未果。

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

概率和那里修正为 M \times \dfrac{1}{M^2} + \dfrac{1}{2}M(M-1) \times \dfrac{2}{M^2} = 1，结果没变。

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

就当我自动约分了（我绝对不会告诉你是我太菜

by Grammar__hbw @ 2024-11-28 18:13:54

qp，Cu ball

by Grammar__hbw @ 2024-11-28 18:14:29

似乎让(x,x)和(x,y)的概率相同就行，但是实现这个有点困难

by Grammar__hbw @ 2024-11-28 18:15:01

另外rp++

by LionBlaze @ 2024-11-28 18:22:09

@Grammar__hbw 两个值的这个 oiwiki 上有

by LionBlaze @ 2024-11-28 18:27:32

@Grammar__hbw 就是首先生成一个 \text{flag}，在 [0,M] 中，如果 \text{flag}=0 那么随机一个 y \in [1,M]，然后区间为 [y,y]，如果 \text{flag} \not = 0 那么就按照刚才错误的方式生成。

容易发现 x = y 时概率为 \dfrac{1}{M+1}\times \dfrac{1}{M} + \dfrac{M}{M+1} \times \dfrac{1}{M^2} = \dfrac{2}{M(M+1)}，x \not = y 时的概率为 \dfrac{M}{M+1} \times \dfrac{2}{M^2} = \dfrac{2}{M(M+1)}

by LionBlaze @ 2024-11-28 18:27:59

好吧其实不容易发现，我推错了一次。但是思路是容易发现的。

by Z_301 @ 2024-11-28 18:33:45

生成长度为 N ，值域在 [1,N+M-1] 的每个数不相同的序列，然后排序，第 i 个减去 i-1 ，是不是就好了 。

| 下一页