随机生成一个不重复序列

robinyqc · 2023-08-23 21:27:29 · 算法·理论

给定连续的值域 V 以及序列长度 n，如何随机生成一个均匀分布的不重复序列？

主要是出题遇到了，思考了一下，很有意思。后来跟着 EarthMessenger 看了 python 源码，又学到了另一种做法。

方法一

不妨来想一下最朴素的算法。我们直接把整个值域装数组，再 shuffle 一下。取前 n 个，就可以做到 O(|V|) 生成了。不过，shuffle 的常数较大，整个过程可以看做 O(|V|w) 的，有没有更好的做法？

其实有一个更朴素的思想，不过有漏洞：直接随机 n 次数字，构成一个序列。这个漏洞就是可能随机出重复的数字。那怎么解决呢？一个简单的做法是先把整个值域放进平衡树，选完直接删掉。那这样复杂度就是 O(|V|+n \log n)，不过阴间常数，肯定不好。解决办法也很简单：把整个值域放进 vector x，然后随一个下标 y，对应元素 x[y] 放进目标 vector z，然后把 x[y] 和 x 末尾元素交换，再 pop 掉就可以了。总复杂度还是 O(|V|+n)，不过由于 rand 之类的有一定常数，整个过程可以看做 O(|V|+nw) 的。由于 n\leq|V|，所以这个做法恒不劣于上面的做法，某些情况优于上面的做法。

分析正确性。假设当前选的是第 i 个数，值域为 n，那么前面所有选择不选到 z 的概率是：

当前选到 z 的概率是 \dfrac 1{n-i+1}。所以 z 被选中的概率是 \dfrac 1n。确实是均匀分布。

方法二

现在是人类智慧时刻。

还是上面那个朴素思想：不考虑重复直接随。遇到重复怎么办？别怕！还记得二次剩余怎么求吗？我们随机一个数字，重了就重了，大不了再选一个呗。就害怕，选了很多次都选到了重复的数字。

不过我们是随机选数字，自带随机化:) 所以算期望就行了。

我们先来解决这样一个问题：

做一件事，每次有 p 的概率失败，1-p 的概率成功。失败后继续尝试直到成功，成功后停止。求成功的期望次数。也就是：

这不就一个等比数列嘛！就是

哎呀！成功的期望次数就是成功的概率分之一！（虽然但是，据说这是经典结论，好像还很直觉 QwQ）

我们要求随机不重复一个数字的复杂度，所以算一个上限就好。上限显然在选第 n 个数的时候达到。此时成功的概率是 \dfrac {|V|-n+1}{|V|}。设 |V|=(n-1)k，那么，期望复杂度是：

那么，我们要选 n 个，总的复杂度就是 O(n\cdot\dfrac k{k-1})。不过，判断一个数是否出现过，由于值域较大，可能需要平衡树来处理，复杂度 O(n\log n\cdot\dfrac k{k-1})。省略掉了 V，巨大进步！！！

缝合怪

但是上面这个算法仍然不能满足所有情况，比方说 n=V 的时候，每次选择都是巨大的代价，期望复杂度都来到了惊人的 O(n^2)。

那么，我们不妨类似整除分块的做法，什么算法更快，采用什么办法。显然，k 较大的时候，采用下面 O(n\log n\cdot\dfrac k{k-1}) 的算法；否则，采用上面 O(|V|+n) 的算法。那具体什么时候呢？稍微解一下下面这个方程就好了。

解得：k\leq \dfrac {\log n+1}2。所以不妨设一个阈值 B=\dfrac {\log n+1}2，当 k\leq B 时，采用上面的做法，否则采用下面的做法。分析一下复杂度。当 k\leq 2 时，|V|=k(n-1)，那么，复杂度是 O(|V|+n)=O(n \log n) 的；当 k>B 时，\dfrac k{k-1}<2，可以看做常数，所以也是 O(n \log n) 的。总复杂度 O(n \log n)。

进一步优化

优化 1

显然我们还可以再优化。比方说，对于 n\log n\geq |V| 的，可以直接采用上面的 O(|V|+n) 的做法，或者用 std::sort 进行时空常数优化。这样，时空复杂度是 O(\min \{|V|,n\log n\}) 的。不过，由于刚才算了合理的阈值，这个优化并不重要。

优化 2

另外一个优化是关于时间复杂度的优化。我们判断一个数是否出现过，不仅可以用 set，还可以用哈希表。这样时间复杂度又会变优，但是时空常数阴间。此时第二个方法的复杂度又会变成 O(n\cdot \dfrac k{k-1}) 的。解一下：

解得：0<k\leq 2。所以设阈值 B=2，当 k\leq B 时，采用上面的做法，否则采用下面的做法。再分析一下复杂度。当 k\leq 2 时，|V|=k(n-1)，k 可以看做常数，那么，复杂度是 O(|V|+n)=O(n) 的；当 k>2 时，\dfrac k{k-1}<2，可以看做常数，所以也是 O(n) 的。总复杂度 O(n)。

优化 3

还是判断一个数是否出现的优化。当 |V| 不大，且空间富余的时候，可以采用常用的 vis 数组判断。使用 std::bitset 可以大幅优化常数。当 |V|\leq 10^8 的时候可以考虑使用这个方法进行常数优化。

优化 4

我们很多情况下不需要那么随机。所以我们可以把值域平均分成 K 块，每块分别求解。这样时间复杂度不变，空间复杂度变为 O(\dfrac nK) 或 O(\dfrac {|V|}K)。

方法三/优化 5

睡觉的时候，又想到一个方法三。具体来说，我们先随机 n 个数，然后排序去重。设现在剩下 m 个数，那么，令 n=m，递归地求解。这个复杂度我不会证，干脆打个表：

            n/V             Exp
         0.0001               1
         0.0002               1
         0.0004               1
         0.0008               1
         0.0016               1
         0.0032               1
         0.0064               2
         0.0128               2
         0.0256               2
         0.0512               3
         0.1024               4
         0.2048               6
         0.4096              11
         0.8192            47.7