随机访问随机排列

Question

我希望生成一个非常大的伪随机置换p : [0,n-1] -> [0,n-1]，然后计算m个特定的值p[i]，其中m << n。是否可能在O(m)的时间内完成此操作？动机是进行大规模并行计算，每个处理器只需要看到一小部分排列，但排列必须在处理器之间保持一致。

请注意，在并行情况下，计算不同集合i值的不同进程不应意外地为i != j产生p[i] == p[j]的结果。

- Geoffrey Irving

---

大部分是与https://dev59.com/Amkw5IYBdhLWcg3wNX73相同的内容。 - Geoffrey Irving

Answer 1

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

生成排列的两种常见算法。Knuth的洗牌算法本质上是顺序的，因此不适合并行处理。另一种是随机选择，并在遇到重复时重新选择。显然，无论以何种顺序应用随机选择，其效果是相同的，因此我提出以下简单算法：

1.对于“Needed”中的每个i（并行），在[0，n-1]中随机抽样候选的p[i]。 2.从“Needed”中删除所有未发生碰撞的条目，以及（可选）从冲突中进行某些确定性选择（例如，如果i <{j | p[j]=p[i]}，则保留p[i]）。 3.使用新的（较小的）集合“Needed”从步骤1开始重复。

由于在这个过程中我们没有失去熵，因此结果本质上等同于以某种不同的顺序从未发生碰撞的位置 i 开始进行顺序随机抽样（我们事先不知道这个顺序）。请注意，如果我们在比较中使用计算出来的值，那么就会引入偏差。

- Jed

---

这个解决方案确实回答了所述的问题，但并没有解决不同的并行进程需要协调选择哪个排列的激励问题。我会编辑问题。 - Geoffrey Irving

Answer 2

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

1. 生成2k = O(1)个[0，n-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 ...))

- Geoffrey Irving

---

"k" 是指什么？ - mako

$k$是一个小整数。但是，这个答案应该被忽略：这里才是真正的答案：http://scicomp.stackexchange.com/questions/4923/random-access-random-permutations - Geoffrey Irving