25

我希望枚举固定空间中数字 1..N 的随机排列。这意味着我无法将所有数字存储在列表中。原因是 N 可能非常大，超过可用内存。我仍然希望能够一次遍历这样一个数字排列，每个数字只访问一次。

我知道对于某些 N 可以做到这一点：许多随机数生成器随机但完全地循环遍历它们的整个状态空间。状态大小为 32 位的良好随机数生成器将发出数字 0..(2^32)-1 的排列。每个数字恰好一次。

例如，我想选择 N 为任何数字，而不是受限于 2 的幂。有这个算法吗？

4

6 回答 6

11

最简单的方法可能是只为比您关心的更大范围创建一个全范围 PRNG，当它生成的数字大于您想要的数字时，只需将其扔掉并获得下一个。

另一种几乎相同的变体的可能性是首先使用线性反馈移位寄存器（LFSR）来生成数字。这有几个优点：首先，LFSR 可能比大多数 PRNG 快一点。其次，（我相信）设计一个产生接近您想要的范围的数字的 LFSR 会更容易一些，并且仍然确保它以（伪）随机顺序循环其范围内的数字，没有任何重复。

无需在细节上花费大量时间，LFSR 背后的数学就已经得到了相当彻底的研究。生成一个遍历其范围内所有数字而不重复的数字，只需要选择一组对应于不可约多项式的“抽头”。如果您不想自己搜索，可以很容易地找到几乎任何合理大小的已知表格（例如，快速浏览一下，维基百科文章列出了它们最大 19 位的大小）。

如果没有记错的话，至少有一个可能的位大小的不可约多项式。这意味着在最坏的情况下，您可以创建一个生成器，其范围大约是您需要的两倍，因此平均而言，您会（大约）丢弃您生成的所有其他数字。鉴于 LFSR 的速度，我猜你可以做到这一点并且仍然保持相当可接受的速度。

于 2012-04-07T13:49:31.400 回答
10

一种方法是

  1. 找到一个p大于的素数N，最好不要大很多。
  2. g求单位模的原根p，即一个数1 < g < p，g^k ≡ 1 (mod p)当且仅当k是 的倍数p-1。
  3. 遍历g^k (mod p)for k = 1, 2, ...，忽略大于 的值N。

对于每个素数p，都有φ(p-1)统一的原始根，所以它有效。但是，可能需要一段时间才能找到。一般来说，找到一个合适的素数要容易得多。

为了找到一个原始根，我知道什么比试错更好，但是可以通过p适当地选择素数来增加快速找到的概率。

由于原根的数量是φ(p-1)，如果r在 1 到 的范围内随机选择，那么p-1直到找到原根的预期尝试次数是，因此(p-1)/φ(p-1)应该选择相对较大的，这意味着必须有很少的不同素数除数（最好只有大除数，因子 2 除外）。pφ(p-1)p-1

除了随机选择，还可以按顺序尝试是否2, 3, 5, 6, 7, 10, ...是一个原始根，当然跳过完美幂（或者不，它们通常很快被消除），这应该不会对所需的尝试次数造成很大影响。

所以它归结为检查一个数字是否x是一个原始根模p。如果p-1 = q^a * r^b * s^c * ...有不同的素数q, r, s, ...，x是原根当且仅当

x^((p-1)/q) % p != 1
x^((p-1)/r) % p != 1
x^((p-1)/s) % p != 1
...

因此需要一个体面的模幂运算（通过重复平方的幂运算非常适合，每一步都减少模数）。和一个很好的方法来找到的主要因素分解p-1。但是请注意，即使是简单的试除法也只有 O(√p)，而置换的生成是 Θ(p)，因此分解是最优的并不是最重要的。

于 2012-04-07T13:42:34.973 回答
4

另一种方法是使用分组密码。有关详细信息，请参阅此博客文章。

该博客发布了论文Ciphers with Arbitrary Finite Domains的链接，其中包含一系列解决方案。

于 2012-04-11T05:32:11.310 回答
3

考虑素数 3。要充分表达所有可能的输出，请这样想...

bias + step mod prime

这bias只是一个偏移偏差。step是一个累加器（1例如，它只是按0, 1, 2顺序排列，而2结果是0, 2, 4）并且prime是我们想要生成排列的素数。

例如。一个简单的序列0, 1, 2将是......

0 + 0 mod 3 = 0
0 + 1 mod 3 = 1
0 + 2 mod 3 = 2

修改其中的几个变量一秒钟，我们将采用biasof1和stepof 2（仅用于说明）...

1 + 2 mod 3 = 0
1 + 4 mod 3 = 2
1 + 6 mod 3 = 1

你会注意到我们制作了一个完全不同的序列。集合中没有数字重复，所有数字都被表示（它是双射的）。偏移和偏差的每个独特组合将导致prime! 该集合的一种可能排列。在你的情况下prime，3你会看到有6不同的可能排列：

0,1,2
0,2,1
1,0,2
1,2,0
2,0,1
2,1,0

如果你对上面的变量进行数学运算，你不会认为它会产生相同的信息要求......

1/3! = 1/6 = 1.66..

……对……

1/3 (bias) * 1/2 (step) => 1/6 = 1.66..

限制很简单，bias必须在范围内0..P-1并且step必须在范围内（我在自己的工作中1..P-1一直在使用0..P-2和添加算术）。1除此之外，它适用于所有素数，无论它们有多大，并且将排列它们的所有可能的唯一集合，而不需要超过几个整数的内存（每个在技术上比素数本身需要的位数略少）。

请注意，此生成器并非旨在用于生成数量上不是素数的集合。这样做是完全有可能的，但不建议出于安全敏感的目的，因为它会引入定时攻击。

也就是说，如果您想使用此方法生成一个非素数的集合序列，您有两个选择。

首先（也是最简单/最便宜的），选择比您正在寻找的集合大小稍大的素数，并让您的生成器简单地丢弃任何不属于的东西。再一次，危险，如果这是一个安全敏感的应用程序，这是一个非常糟糕的主意。

其次（迄今为止最复杂和最昂贵的），您可以认识到所有数字都由质数组成，并创建多个生成器，然后为集合中的每个元素生成一个乘积。换句话说，一个nof6将涉及所有可能匹配的素数生成器6（在这种情况下，2和3），按顺序相乘。这既昂贵（尽管在数学上更优雅）也引入了定时攻击，因此更不推荐使用。

最后，如果你需要一个生成器bias和或step......你为什么不使用同一系列的另一个:)。突然之间，您非常接近于创建真正的简单随机样本（通常这并不容易）。

于 2017-03-26T03:28:55.607 回答
2

LCG（x=(x*m+c)%b样式生成器）的根本弱点在这里很有用。

如果生成器是正确形成的，那么x%f它也是所有低于的值的重复序列f（f如果因子为b）。

由于b通常是 2 的幂，这意味着您可以采用 32 位生成器并通过屏蔽最高位将其减少为 n 位生成器，并且它将具有相同的全范围属性。

这意味着您可以通过选择适当的掩码将丢弃值的数量减少到少于 N。

不幸的是，由于与上面给出的完全相同的原因，LCG 是一个糟糕的生成器。

此外，这与我在@JerryCoffin 的回答的评论中指出的完全相同的弱点。它总是会产生相同的序列，而种子控制的唯一事情是在该序列中从哪里开始。

于 2017-09-15T17:23:12.073 回答
0

这是一些SageMath代码，应该按照Daniel Fischer 建议的方式生成随机排列：

def random_safe_prime(lbound):
    while True:
        q = random_prime(lbound, lbound=lbound // 2)
        p = 2 * q + 1
        if is_prime(p):
            return p, q


def random_permutation(n):
    p, q = random_safe_prime(n + 2)

    while True:
        r = randint(2, p - 1)
        if pow(r, 2, p) != 1 and pow(r, q, p) != 1:
            i = 1
            while True:
                x = pow(r, i, p)
                if x == 1:
                    return

                if 0 <= x - 2 < n:
                    yield x - 2

                i += 1
于 2018-03-09T13:18:27.877 回答