使用PRNG而不是改组来生成随机范围

在给定任意种子值的情况下,是否有任何已知的算法可以在线性时间和常数空间(当迭代生成输出时)生成混洗范围[0..n]？

假设n可能很大,例如数百万,因此不需要潜在地产生每种可能的排列,尤其是因为它是不可行的(种子值空间需要很大).这也是需要恒定空间的原因.(所以,我特别不是在寻找一种阵列混洗算法,因为这需要将范围存储在长度为n的数组中,因此会使用线性空间.)

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

理想情况下,它的行为类似于具有周期和范围的LCGn,但选择a和c制作LCG 的艺术是微妙的.只要满足约束a,并c在一个完整周期LCG可满足我的要求,但如果有更好的想法在那里我想知道.

基于Jason的回答,我在C#中做了一个简单直接的实现.找到大于N的下一个最大幂2.这使得生成a和c变得微不足道,因为c需要相对素数(意味着它不能被2整除,也就是奇数),并且(a-1)需要可以被2整除,并且(a-1)需要被4整除.从统计上来说,它应该需要1-2个同余来生成下一个数字(因为2N> = M> = N).

class Program
{
    IEnumerable 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();
    }
}

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,