Generating random permutations without storing additional arrays. Given a list of size N, I would like to generate many random permutations without having to store each permutation entirely in memory. I would like to be able to calculate the next item in a given permutation, or be able to access the i-th item in a given permutation.
The permutations only have to feel random, and don't have to be cryptographically secure in any way. It is important that each element appears exactly once in each permutation.
Something like this:
getItem(initialList, randomSeed, index);
getNextItem(initialList, currentItem);
Are there any existing algorithms that could be used to implement this?
Some clarifications from the questions below:
Each permutation is independent, and it is okay if two permutations end up identical.
I need to be able to access values from multiple permutations at the same time. As an example, I might generate 10 permutations of the same initial list and then use values from each of them simultaneously.
 A: Since you allow duplicate permutations, given an array $A[\cdot]$ of such items of length $n$, we produce any random permutation $P$ by the following algorithm:


*

*$P \leftarrow A$

*for $k \in N,N-1...1$:


*

*pick $r(1,k)$ to be random integer between $1$ and $k$

*swap $P[k]$ and $P[r(1,k)]$



This is linear in space in time, but if you don't count incoming and outgoing space, it is constant in space.
All permutations are reproducible if you can reproduce the seed from which you started generating the random numbers.
A: If the solution must use constant space, then there is no hope of picking a permutation randomly and then remembering which permutation you picked. There are $N!$ possibilities for a permutation, and if we assume that $N$ can be represented by one word of our machine, then remembering a permutation (whether by writing down the corresponding permutation of $\{1,2,\dots,N\}$, or by something like a Lehmer code) will take $O(N)$ words.
One alternative is to severely restrict the set of permutations that can be generated. For example, if $N$ is prime, we can consider the $N(N-1)$ different permutations of $\{0,1,\dots,N-1\}$ given by 
$$
    (a, a+b \bmod N, a+2b \bmod N, a+3b \bmod N, \dots, a + (N-1)b \bmod N)
$$
for arbitrary $a \in \{0,1,\dots,N-1\}$ and $b \in \{1,2,\dots,N-1\}$. This is a set of permutations that at least has the following slight randomness property:


*

*For any $i$, the $i^{\text{th}}$ element of the permutation is equally likely to be any element.

*For any $i$ and $j$, if we know the $i^{\text{th}}$ element of the permutation, the $j^{\text{th}}$ element of the permutation is still equally likely to be any other element.


We can pick a random permutation by choosing $a$ and $b$ at random, and having done so, it's easy to take the $i^{\text{th}}$ element in the permutation for any $i$. Only $a$ and $b$ have to be stored.
When $N$ is not prime, we can approximate this solution by restricting $b$ to elements of $\{1,2,\dots,N-1\}$ that are relatively prime to $N$, but this no longer has quite as nice a pairwise independence property. When $N$ is at least square-free (a product of distinct primes $p_1 \dotsb p_k$) a slightly more complicated solution preserving pairwise independence is to generate a random permutation of $\{0,1,\dots,p_i-1\}$ for each $i$, and glue them together using the Chinese remainder theorem.
More generally, you can look into permutation polynomials: polynomial functions $f$ such that the sequence
$$
    f(0) \bmod N, f(1) \bmod N, \dots, f(N-1)\bmod N
$$
is a permutation of $\{0,1,\dots,N-1\}$. If we have a large family of permutation polynomials, we can pick a random polynomial from that family, store it, and be able to access any element of the corresponding permutation very quickly.
