1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's not really possible to do this unless you keep track of the numbers you used already (i.e. keep track of the permutation so far). Is that allowed? $\endgroup$ – Alex R. Nov 15 '17 at 22:13
  • $\begingroup$ It's not about allowed or not allowed, but just trying to find the best solution. :) $\endgroup$ – Anthony Nov 15 '17 at 22:21
  • 1
    $\begingroup$ do you allow repetitions in your permutations? i.e. generating 3 permutations of $abc$ can you use $abc, bac$ and $abc$ with 1st and 3rd being the same? $\endgroup$ – gt6989b Nov 15 '17 at 22:21
  • $\begingroup$ @gt6989b The permutations are totally independent. it is fine if two or more end up being the same. $\endgroup$ – Anthony Nov 15 '17 at 22:22
  • $\begingroup$ @Anthony: Could you answer my question though? Are you able to keep track of the permutation so far? i.e. imagine you've drawn (1,6,2) so far and now wanna get the 4'th element (which can be either 3,4,5 if n=6) $\endgroup$ – Alex R. Nov 15 '17 at 22:22
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If N is not prime, could I just use the next prime number larger than N and skip and elements that are greater than N? It looks like this method should give N * (N - 1) different permutations. $\endgroup$ – Anthony Nov 16 '17 at 19:13
  • $\begingroup$ I guess if you're only accessing elements of the permutation sequentially, you could do that (and keep track of the number of times you skipped an element). It wouldn't work if you were trying to access the 1000th, then the 10th, then the 200th element of the permutation; you'd have to figure out how many elements got skipped to do that. $\endgroup$ – Misha Lavrov Nov 16 '17 at 20:57
  • $\begingroup$ Awesome, thanks. This does exactly what I need. ^.^ $\endgroup$ – Anthony Nov 17 '17 at 4:20
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If I understand this correctly, this produces a single permutation by modifying the initial array? I need to be able to access values from multiple permutations at the same time. $\endgroup$ – Anthony Nov 15 '17 at 22:34
  • $\begingroup$ @Anthony yes, you are correct. but you can just reset the seed for each permutation, and regenerate it at will. E.g., have first permutation start with seed 1, second with seed 2, etc. $\endgroup$ – gt6989b Nov 15 '17 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.