我想尽快生成一个随机排列。 问题:O(n) 的 knuth 洗牌涉及生成 n 个随机数。 由于生成随机数非常昂贵。 我想找到一个涉及固定 O(1) 数量的随机数的 O(n) 函数。
我知道这个问题以前有人问过，但我没有看到任何相关的答案。
只是强调一点:我不是在寻找小于 O(n) 的算法，而是一种涉及更少随机数生成的算法。
谢谢
最佳答案
创建每个排列到从 1 到 n 的数字的 1-1 映射! (阶乘)。生成一个1到n!的随机数，使用映射，得到排列。
对于映射，也许这会很有用:http://en.wikipedia.org/wiki/Permutation#Numbering_permutations
当然，这很快就会失控，因为 n!很快就会变得非常大。
关于algorithm - 随机排列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3079633/