使用伪随机数生成器生成乱序范围，而不是通过洗牌实现

Question

使用伪随机数生成器生成乱序范围，而不是通过洗牌实现

algorithmlanguage-agnosticrandomshuffle

25

有没有已知的算法可以在线性时间和常数空间内（迭代产生输出时），用任意种子值生成一个洗牌范围[0..n)？

假设n可能很大，例如数百万，因此不需要潜在地生成每个可能的排列，特别是因为这是不可行的（种子值空间需要巨大）。这也是常数空间要求的原因。（因此，我特别不寻找数组洗牌算法，因为它要求将范围存储在长度为n的数组中，因此会使用线性空间。）

我知道问题162606，但它没有回答这个特定的问题-该问题中给出的从排列索引到排列的映射将需要巨大的种子值空间。

理想情况下，它将像LCG一样具有周期和范围n，但是选择a和c的艺术很微妙。仅满足全周期LCG的a和c的约束可能满足我的要求，但我想知道是否有更好的想法。

- Barry Kelly

你想输出整个范围还是只输出其中的一些元素？ - Pete Kirkham

范围有多大：一开始我不知道。这是可配置的。它可能只是完整范围的一小部分，但可能是例如10001范围中的10000个项目，因此仅选择随机项目并测试重复项不是一个好方法。 - Barry Kelly

5个回答

7

这是一个Python实现的线性同余生成器，来自FryGuy的答案。因为我需要写它，而且认为它可能对其他人有用。

import random
import math

def lcg(start, stop):
    N = stop - start

    # M is the next largest power of 2
    M = int(math.pow(2, math.ceil(math.log(N+1, 2))))

    # c is any odd number between 0 and M
    c = random.randint(0, M/2 - 1) * 2 + 1

    # M=2^m, so make (a-1) divisible by all prime factors and 4
    a = random.randint(0, M/4 - 1) * 4 + 1

    first = random.randint(0, M - 1)
    x = first
    while True:
        x = (a * x + c) % M
        if x < N:
            yield start + x
        if x == first:
            break

if __name__ == "__main__":
    for x in lcg(100, 200):
        print x,

- Day

6

听起来你想要一个算法，它可以保证从0到n-1产生一个不重复的循环。根据你的需求，几乎肯定有许多这样的算法；如果你想深入了解其背后的理论，那么群论将是最有帮助的数学分支。

如果你想要快速且不关心可预测性/安全性/统计模式，那么LCG可能是最简单的方法。你链接的维基百科页面包含了以下（相当简单）的要求：

LCG的周期最多为m，并且对于一些选择的a，要小得多。仅当满足以下条件时，LCG才会具有完整的周期：

1. c和m互质， 2. a - 1被m的所有质因子整除 3. 如果m是4的倍数，则a - 1是4的倍数

或者，你可以选择一个周期N >= n，其中N是具有方便的数字属性的最小值，并且只需丢弃在n和N-1之间产生的任何值。例如，最低N = 2^k - 1 >= n将使你可以使用线性反馈移位寄存器（LFSR）。或者找到你喜欢的加密算法（RSA、AES、DES等），并给定一个特定的密钥，找出它置换的数字空间N，并在每个步骤中应用一次加密。

如果n很小但你想要高安全性，那可能是最棘手的情况，因为任何序列S的周期N很可能比n高得多，但是也不容易推导出一个具有比N更短周期的非重复数字序列。（例如，如果你可以保证S mod n的输出是非重复数字序列，那么这将泄露S的信息，攻击者可能会利用这个信息）

- Jason S

3

查看我的文章《使用分块密码实现安全置换》，其中介绍了一种方法。

- Arachnid

1

研究线性反馈移位寄存器，它们可以用于正好这个目的。简单地解释一下，您从种子开始，然后使用公式进行迭代。

x = (x << 1) | f(x)

其中f(x)只能返回0或1。

如果您选择一个好的函数f，x将以良好的伪随机方式循环遍历1到2^n-1（其中n是某个数字）之间的所有值。可以在这里找到示例函数，例如，对于63个值，您可以使用以下函数：

f(x) = ((x >> 6) & 1) ^ ((x >> 5) & 1)

- erikkallen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- FryGuy · Accepted Answer

基于Jason的回答，我在C＃中进行了简单明了的实现。找到大于N的下一个最大的2的幂次方。这使得生成a和c变得非常容易，因为c需要是相对质数（意味着它不能被2整除，也就是奇数），而（a-1）需要被2整除，并且（a-1）需要被4整除。从统计上讲，生成下一个数字应该只需要1-2个同余式（因为2N>=M>=N）。

class Program
{
    IEnumerable<int> GenerateSequence(int N)
    {
        Random r = new Random();
        int M = NextLargestPowerOfTwo(N);
        int c = r.Next(M / 2) * 2 + 1; // make c any odd number between 0 and M
        int a = r.Next(M / 4) * 4 + 1; // M = 2^m, so make (a-1) divisible by all prime factors, and 4

        int start = r.Next(M);
        int x = start;
        do
        {
            x = (a * x + c) % M;
            if (x < N)
                yield return x;
        } while (x != start);
    }

    int NextLargestPowerOfTwo(int n)
    {
        n |= (n >> 1);
        n |= (n >> 2);
        n |= (n >> 4);
        n |= (n >> 8);
        n |= (n >> 16);
        return (n + 1);
    }

    static void Main(string[] args)
    {
        Program p = new Program();
        foreach (int n in p.GenerateSequence(1000))
        {
            Console.WriteLine(n);
        }

        Console.ReadKey();
    }
}