algorithm - 使用PRNG而不是改组生成改组范围

给定一个任意的种子值，是否有任何已知的算法可以在线性时间和恒定空间(当输出迭代产生时)中产生一个改组范围[0..n]？

假设n可能很大，例如在数以百万计的人中，因此不需要潜在地产生所有可能的排列的要求，尤其是因为它是不可行的(种子值(value)空间将是巨大的)。这也是需要恒定空间的原因。 (因此，我并不是特别在寻找数组改组算法，因为这需要将范围存储在长度为n的数组中，因此会使用线性空间。)

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

理想情况下，它的作用类似于带有n的周期和范围的LCG，但是为LCG选择a和c的技巧很微妙。在一个完整的LCG中仅满足a和c的约束可能满足我的要求，但是我想知道是否还有更好的主意。

最佳答案

基于Jason's answer，我用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();
    }
}