Generate random permutation of huge list (in Python)
algorithm, iterator, permutation, python
Solution
One possibility is to use an encryption. Since encryption is reversible, i.e. one-to-one, for a given key you will get back the same numbers you encrypt but in a different order.
You need a block cypher with a block size large enough to include your maximum N. Use DES in ECB mode for N = 2^64 - 1. Use AES in ECB mode for N = 2^128 - 1. For other sizes, either use Hasty Pudding cipher, which has variable block size, or write your own simple Feistel cipher. I assume that you just need a shuffle, not a cryptographically secure shuffle.
If the output is greater than N, then just re-encrypt until it is less than N, the 1-to-1 property ensures that the chain of large numbers is also unique.
There is no need to store the entire array in memory, each number can be encrypted as needed. Just the key and the cipher algorithm are needed. One slight complication is that block ciphers work on [0 ... N-1]; you might need some extra code to deal with the extremes.
Problem
I'd like to create a random permutation of the numbers `[1,2,...,N]` where `N` is a big number. So I don't want to store all elements of the permutation in memory, but rather iterate over the elements of my particular permutation without holding former values in memory. Any idea how to do that in Python?