random - 随机存取随机排列

Question

我想生成一个非常大的伪随机排列 p：[0,n-1] -> [0,n-1]，然后计算 m 个特定值 p[i]，其中 m << n。是否有可能在 O(m) 时间内做到这一点？动机是大型并行计算，其中每个处理器只需要查看一小部分排列，但排列必须在处理器之间保持一致。

请注意，为了在并行情况下有所帮助，计算不相交的 i 值集的不同进程不应意外地为 i != j 生成 p[i] == p[j]。

Answer 1

编辑：有一个基于分组密码的更聪明的算法，我认为 Geoff 会写出来。

有两种常见的算法来生成排列。Knuth 的 shuffle 本质上是顺序的，因此不是并行性的好选择。另一种是随机选择并在遇到重复时重试。随机选择在以任何顺序应用时显然是等效的，因此我提出以下简单算法：

1. 为每个p[i]in （并行）随机抽样候选。[0,n-1]iNeeded
2. 从 中删除所有非冲突条目Needed，以及（可选地）从冲突中删除一些确定性选择（例如，保留p[i]if i < {j | p[j] = p[i]}）。
3. 使用新的（较小的） set 从步骤 1 重复Needed。

由于我们在这个过程中没有丢失熵，结果本质上相当于以某种不同的顺序进行顺序随机采样，从i没有碰撞的位置开始（我们只是事先不知道那个顺序）。请注意，如果我们在比较中使用计算值，例如，我们会引入偏差。

Answer 2

一个非常低强度版本的示例：

1. 在 [0,n-1] 中生成 2k = O(1) 个随机整数 a_i,b_i，其中 a_i 与 n 互质。
2. 选择一个弱排列 wp : [0,n-1] -> [0,n-1], 说 w(i) = i 除了高位翻转之外。
3. p[i] = b_0 + a_0 * wp(b_1 + a_1 * wp(... i ...))