随机排列

Question

我想尽可能快地生成随机排列.问题:作为O(n)的knuth shuffle涉及生成n个随机数.由于生成随机数非常昂贵.我想找到一个涉及固定O(1)量随机数的O(n)函数.

我意识到之前已经问过这个问题,但我没有看到任何相关的答案.

只是强调一点:我不是在寻找比O(n)更少的东西,只是一个涉及较少生成随机数的算法.

谢谢

Answer 1

创建每个排列的1-1映射到从1到n的数字!(n阶乘).在1到n!中生成一个随机数,使用映射,得到排列.

当然,这会很快失控,就像n!很快就会变得很大.

是的，就所需的随机性而言，这是最佳算法。具体有多大： log(n!) 实际上是 O(n log n) 的斯特林近似值，因此我们需要为此生成大约 n log n 位。这当然是最优的；我们无法生成少于 log(n!) 位的完美均匀分布的排列。 (2认同)
+1(我有同样的想法),但如果生成'N`随机数太贵(不知何故),那么也许`N`非常庞大,在`[1..N!]`范围内生成1个随机数可能不是'O(1)`.映射也可能涉及划分,这种操作可能不是这个规模的"O(1)". (2认同)
如果你的算法的行为完全由 32 位状态决定，那么只能生成 2^32 种排列——大量的剩余排列*永远不会*生成。2^32 甚至小于 13！，2^64 小于 21！…您需要*至少* 525 位来生成 100 个元素的随机排列。 (2认同)