Python: Generating a big uniform permutation cheaply

Question

I'm not sure whether this is possible even theoretically; but if it is, I'd like to know how to do it in Python.

I want to generate a big, random permutation cheaply. For example, say that I want a permutation on range(10**9). I want the permutation to be uniform (i.e. I want the numbers to be all over the place without any seeming structure.) I want to have a function available to get the nth item in the permutation for each n, and I want to have another function available to get the index of every number in the permutation.

And the big, final condition is this: I want to do all of that without having to store all the items of the permutation. (Which can be a huge amount of space.) I want each item to be accessible, but I don't want to store all the items, like range in Python 3.

Is this possible?

Answer 1

I believe that a block cipher, like AES, provides exactly this functionality.

Answer 2

The only way I can see this happening and partially fulfilling your requirements is if the permutation is not random but looks random, and is really a series from which you can generate a_n if you know a_n-1.

Take a look at this: http://en.wikipedia.org/wiki/Linear_feedback_shift_register What you want is a maximum length LSFR. It will generate all numbers for 0 to 2**n-1 once, in a seemingly random order. For different n you need to use a different function.

I think you can't have functions getIdxOf(val) and getValOf(Idx) however, unless you just go through the generating functions one by one.