我想生成一个非常大的伪随机排列 p : [0,n-1] -> [0,n-1]，然后计算 m 个特定值 p[i]，其中 m
请注意，为了在并行情况下提供帮助，计算不相交的 i 值集的不同进程不应意外生成 p[i] == p[j]（对于 i != j）。
编辑：还有更多基于分组密码的巧妙算法 http://blog.notdot.net/2007/9/Damn-Cool-Algorithms-Part-2-Secure-permutations-with-block-ciphers我认为杰夫会写下来。
有两种常见的生成排列的算法。 Knuth 的洗牌本质上是顺序的，因此对于并行性来说不是一个好的选择。另一种是随机选择，只要遇到重复就重试。以任何顺序应用时，随机选择显然是等效的，因此我提出以下简单算法：
- 随机抽取候选者
p[i] in [0,n-1]对于每个i in Needed（在平行下）。
- 删除所有非冲突条目
Needed，以及（可选）碰撞中的一些确定性选择（例如，保持p[i] if i < {j | p[j] = p[i]}).
- 使用新的（较小的）集合重复步骤 1
Needed.
由于我们在此过程中没有丢失熵，因此结果本质上相当于以某种不同顺序进行的顺序随机采样，从位置开始i这并没有发生碰撞（我们只是事先不知道这个顺序）。请注意，例如，如果我们在比较中使用计算值，我们就会引入偏差。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
