Iterating shuffled [0..n) without arrays

Question

I know of a couple of routines that work as follows:

X_n+1 = Routine(X_n, max)

For example, something like a LCG generator:

X_n+1 = (a*X_n + c) mod m

There isn't enough parameterization in this generator to generate every sequence.

Dream Function:

X_n+1 = Routine(X_n, max, permutation number)

This routine, parameterized by an index into the set of all permutations, would return the next number in the sequence. The sequence may be arbitrarily large (so storing the array and using factoradic numbers is impractical.

Failing that, does anyone have pointers to similar functions that are either stateless or have a constant amount of state for arbitrary 'max', such that they will iterate a shuffled list.

Answer 1

There are n! permutations of n elements. Storing which one you're using requires at least log(n!) / log(2) bits. By Stirling's approximation, this takes roughly n log(n) / log (2) bits.

Explicitly storing one index takes log(n) / log(2) bits. Storing all n, as in an array of indices takes n times as many, or again n log(n) / log(2). Information-theoretically, there is no better way than explicitly storing the permutation.

In other words, the index you pass in of what permutation in the set you want takes the same asymptotic storage space as just writing out the permutation. If, for, example, you limit the index of the permutation to 32 bit values, you can only handle permutations of up to 12 elements. 64 bit indices only get you up to 20 elements.

As the index takes the same space as the permutation would, either change your representation to just use the permutation directly, or accept unpacking into an array of size N.