c++ - 随机排列中第 n 项的高效计算

Question

想象一下，我能够使用诸如 Knuth 洗牌之类的方法和使用 key 播种的种子随机数生成器来洗牌 0 到 2^32 之间的所有数字。

从概念上讲，我需要两个数组(使用 Z₅ 而不是 Z_2³² 为简洁起见):

[2, 0, 1, 4, 3] // perm
[1, 2, 0, 4, 3] // inv === p^-1

如果我有这些数组，我可以高效地查找排列中的第 n 个元素，并找出 purmutation 值 v 中的元素；

v = perm[n];
n == inv[v]; // true

我不想存储两个 16 GB 的 uint 数组来表示这个打乱后的集合，因为我对整个打乱后的序列在任何时候都不感兴趣。我只对第 n 个元素的值感兴趣。

理想情况下，我想编写两个像这样工作的纯函数:

uint nthShuffled = permutate<uint>(key, n); // O(log n)
uint n == invert<uint>(key, nthShuffled); // O(log n)

要求:

• 每个 32 位值都映射到一个唯一的不同 32 位值。
• 排列中前 100 个元素的知识无法提供有关排列中第 101 个元素可能是什么的信息。

我明白理论上至少要有2³²!唯一键来表示任何可能的排列，但我相信我可以在实践中将这个问题隐藏在一个好的散列函数后面。

有没有什么东西可以接近这个？

Answer 1

任何分组密码实际上都是伪随机排列。一个 32 位 block 密码排列 0 和 2 ^ 32 - 1 之间的整数。

给定一个 key ，用这个 key 加密 N 得到 N-th 伪随机数。

唯一的问题是找到一个好的 32 位分组密码。我唯一知道的是 SKIP32 ，但我不知道它的强度。

SKIP32 的密​​钥大小为 80 位。如果它是一个好的密码，那就足够了。

不过，我还是不知道密码。

如果将范围增加到 2 ^ 64 - 1 整数是您的一个选项，您可以简单地使用众所周知的 64 位分组密码，例如 Triple- DES 或 Blowfish。