Generating shuffled range using a PRNG rather than shuffling

Question

Is there any known algorithm that can generate a shuffled range [0..n) in linear time and constant space (when output produced iteratively), given an arbitrary seed value?

Assume n may be large, e.g. in the many millions, so a requirement to potentially produce every possible permutation is not required, not least because it's infeasible (the seed value space would need to be huge). This is also the reason for a requirement of constant space. (So, I'm specifically not looking for an array-shuffling algorithm, as that requires that the range is stored in an array of length n, and so would use linear space.)

I'm aware of question 162606, but it doesn't present an answer to this particular question - the mappings from permutation indexes to permutations given in that question would require a huge seed value space.

Ideally, it would act like a LCG with a period and range of n, but the art of selecting a and c for an LCG is subtle. Simply satisfying the constraints for a and c in a full period LCG may satisfy my requirements, but I am wondering if there are any better ideas out there.

Answer 1

Sounds like you want an algorithm which is guaranteed to produce a cycle from 0 to n-1 without any repeats. There are almost certainly a whole bunch of these depending on your requirements; group theory would be the most helpful branch of mathematics if you want to delve into the theory behind it.

If you want fast and don't care about predictability/security/statistical patterns, an LCG is probably the simplest approach. The wikipedia page you linked to contains this (fairly simple) set of requirements:

The period of a general LCG is at most m, and for some choices of a much less than that. The LCG will have a full period if and only if:

1. c and m are relatively prime,
2. a - 1 is divisible by all prime factors of m
3. a - 1 is a multiple of 4 if m is a multiple of 4

Alternatively, you could choose a period N >= n, where N is the smallest value that has convenient numerical properties, and just discard any values produced between n and N-1. For example, the lowest N = 2^k - 1 >= n would let you use linear feedback shift registers (LFSR). Or find your favorite cryptographic algorithm (RSA, AES, DES, whatever) and given a particular key, figure out the space N of numbers it permutes, and for each step apply encryption once.

If n is small but you want the security to be high, that's probably the trickiest case, as any sequence S is likely to have a period N much higher than n, but is also nontrivial to derive a nonrepeating sequence of numbers with a shorter period than N. (e.g. if you could take the output of S mod n and guarantee nonrepeating sequence of numbers, that would give information about S that an attacker might use)

Answer 2

Based on Jason's answer, I've made a simple straightforward implementation in C#. Find the next largest power of two greater than N. This makes it trivial to generate a and c, since c needs to be relatively prime (meaning it can't be divisible by 2, aka odd), and (a-1) needs to be divisible by 2, and (a-1) needs to be divisible by 4. Statistically, it should take 1-2 congruences to generate the next number (since 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();
    }
}

Answer 3

See my article on secure permutations with block ciphers for one way to do it.

Answer 4

Look into Linear Feedback Shift Registers, they can be used for exactly this. The short way of explaining them is that you start with a seed and then iterate using the formula

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

where f(x) can only return 0 or 1.

If you choose a good function f, x will cycle through all values between 1 and 2^n-1 (where n is some number), in a good, pseudo-random way. Example functions can be found here, e.g. for 63 values you can use

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