在恒定空间中创建1..N的随机排列

Question

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

我知道这可以为某个N来完成：许多随机数生成周期通过他们的整个状态空间随机，而是完全。状态大小为32位的好随机数发生器将发出数字0 ...（2^32）-1的置换。每一个数字只有一次。

我想挑电量为任意数量在所有的，而不是被限制在例如2的幂。有没有这样的算法？

Answer 1

最简单的方法可能是只创建一个全范围的PRNG为更大范围的比你所关心的，当它产生比你想有一个较大的数目，只是把它扔掉，并得到下一个。

这几乎是同一的变体的另一种可能性是使用线性反馈移位寄存器（LFSR）在第一位置，以产生数字。这有两个好处：首先，LFSR可能比大多数PRNG快一点。其次，（我相信）设计一个LFSR更容易，它可以产生接近你想要的范围的数字，并且仍然可以确保它循环遍历（伪）随机顺序的范围内的数字，而不需要重复。

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

如果内存服务，至少有一个不可约多项式的可能位大小。这意味着在最糟糕的情况下，您可以创建一个发电机，其大小是您需要的范围的两倍，因此平均而言，您将大致丢弃您生成的每个其他数字。考虑到LFSR的速度，我想你可以做到这一点，仍然保持相当可接受的速度。

Answer 2

一种方式做这将是

1. 找到比N大的黄金p，最好不要大得多。
2. 查找统一g模p的原根，即，一些1 < g < p使得g^k ≡ 1 (mod p)当且仅当是k的p-1的倍数。
3. 转到通过g^k (mod p)为k = 1, 2, ...，忽略了比N较大的值。

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

为了找到一个原始根，我没有什么比反复试验更好，但是可以通过适当地选择素数来提高快速查找的概率。

由于原始根的个数为φ(p-1)，如果一个随机地从1到p-1范围选择r，尝试的预期数量，直到一个找到一个原始根是(p-1)/φ(p-1)，因此应该选择p使得φ(p-1)相对大，这意味着p-1必须具有几个不同的素因子（和优选地仅路数，除了因子2）。

不是随机选择，也可以按顺序尝试是否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），所以它不是最重要的因数分解是最佳的。

Answer 3

另一种方法是使用分组密码;详情请参阅this blog post。

的博客文章链接，其中包含了一堆方案的纸张Ciphers with Arbitrary Finite Domains。

Answer 4

考虑的首要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 

修改夫妇第二这些变量，我们将采取的1bias和2（只是为了演示）step ...

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

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

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

如果你对变量的数学上面你不会认为它会导致同样的信息需求.. 。

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

... ... VS

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

限制很简单，bias必须在0..P-1和step必须在1..P-1（我一直在功能上刚刚被使用0..P-2和算术加1在我自己的工作中）。除此之外，它可以处理所有素数，不管它有多大，并且会排列所有可能的独特集合，而不需要超过几个整数的内存（每个技术要求比素数本身略小）。

注仔细，这种发电机并不意味着可用于生成集，是不是在数量上黄金。完全可以这样做，但不建议出于安全敏感的目的，因为它会引入定时攻击。

也就是说，如果你想用这种方法来产生一个不是素数的序列，你有两种选择。

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

二（迄今为止最复杂，成本高），可以识别所有的数字都是由素数的和创建多个生成器，然后生产出的产品在集合中的每个元素。换句话说，n的6将涉及所有可能的匹配6（在这种情况下，2和3）的主要生成器，按顺序相乘。这既昂贵（虽然在数学上更加优雅），并且还引入了定时攻击，所以它甚至不被推荐。

最后，如果你需要一个发电机bias和或step ......为什么你不使用另一个同一个家庭:)。突然间，你非常接近创建真正的简单随机样本（这通常不容易）。

Answer 5

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

如果适当地形成在发电机然后x%f也是所有值的重复序列低于f（提供f如果b一个因子）。

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

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

不幸的是LCG是对完全按照上面给出的相同的原因不良产生。

而且，这种具有完全按照我在@ JerryCoffin的回答评论指出相同的弱点。它将始终产生相同的序列，并且种子控制的唯一内容就是以该序列开始的位置。

Answer 6

下面是一些SageMath应该产生一个随机排列的方式Daniel Fischer suggested：

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