Generating permutations with sub-linear memory

Question

I am wondering if there is a sufficiently simple algorithm for generating permutations of N elements, say 1..N, which uses less than O(N) memory. It does not have to be compute n-th permutation, but it must be able to compute all permutations.

Of course, this algorithm should be a generator of some kind, or use some internal data structure which uses less than O(N) memory, since return the result as a vector of size N already violates the restriction on sub-linear memory.

Ideally

Unless the elements have an already predefined order to them, such as ints such that you can generate the next one when needed, wouldn't just accepting the N number of elements as input already place you at the O(N) memory restriction? – Parkinson

It would, that's why I said the elements are` 1..N`, so that they need not to be passed as an input vector. – Ideally

What about this? O(1) in space, but runtime might be unbounded: Random rnd = ...; List<Integer> l = ...; while (l.size() < N) { int r = 1+rnd.nextInt(N); if(!l.contains(r)) l.add(r) } return l; – Saintjust

Answer 1

Let's assume that the random permutation is being generated one entry at a time. The state of the generator must encode the set of elements remaining (run it to completion) and so, since no possibility can be excluded, the generator state is at least n bits.

Chequerboard

That bound is essentially tight because there's a generator that uses n + O(log n) bits. – Chequerboard

Good point. But what if I am interested in a random permutation, with uniform probability distribution? – Ideally

Answer 2

Maybe you can, with factoradic numbers. You can extract the resulting permutation from it step by step, so you never have to have the entire result in memory.

But the reason I started with maybe, is that I'm not sure what the growing behaviour of the size of the factoradic number itself is. If it fits in an 32bit integer or something like that, N would be limited to a constant so O(N) would equal O(1), so we have to use an array for it, but I'm unsure how big it will be in terms of N.

Ethiopia

Answer 3

I think the answer has to be "no".

Consider the generator for N-element permutations as a state machine: it must contain at a least as many states as there are permutations, else it will start repeating before it finishes generating all of them.

There are N! such permutations, which will require at least ceil(log2(N!)) bits to represent. Stirling's approximation tells us log2(N!) is O(N log N), so we will be unable to create such a generator with sub-linear memory.

Douma

True. But is it possible to generate a random permutation with O(N) memory. The distribution should be uniform, otherwise one could simply always generate 1..N, which is a valid permutation? – Ideally

In order to generate a valid permutation, you will need some way to "remember" which elements have been generated, so you can avoid repeating them. You can do this by keeping a copy of your initial pseudo-random number generator state, and rerunning it for each element generated, to reject duplicate elements. This will reduce the memory requirement to O(log N) bits (to store the current target index) plus the size of the generator state. However, the running time for this method will be at least O(N^2), and average-case (due to many retries for later elements) of O(N^2 log N). – Douma

Note: if the size of the pseudo-random number generator state is smaller than the number of permutations, then some permutations can never be generated. However, a decent PRNG should distribute those permutations it does generate widely, and without a readily discernable pattern... in practice, this should not be a problem. – Douma

Answer 4

The C++ algorithm next_permutation performs an in-place rearrangement of a sequence into its next permutation, or returns false when no further permutations exist. The algorithm is as follows:

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last) {
    if (first == last) return false; // False for empty ranges.
    BidirectionalIterator i = first;
    ++i;
    if (i == last) return false; // False for single-element ranges.
    i = last;
    --i;
    for(;;) {
        BidirectionalIterator ii = i--;
        // Find an element *n < *(n + 1).
        if (*i <*ii) {
            BidirectionalIterator j = last;
            // Find the last *m >= *n.
            while (!(*i < *--j)) {}
            // Swap *n and *m, and reverse from m to the end.
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        // No n was found.
        if (i == first) {
            // Reverse the sequence to its original order.
            reverse(first, last);
            return false;
        }
    }
}

This uses constant space (the iterators) for each permutation generated. Do you consider that linear?

Mayfield

Answer 5

I think that to even store your result (which will be an ordered list of N items) will be O(N) in memory, no?

Anyhow, to answer your later question about picking a permutation at random, here's a technique that will be better than just producing all N! possibilities in a list, say, and then picking an index randomly. If we can just pick the index randomly and generate the associated permutation from it, we're much better off.

We can imagine the dictionary order on your words/permutations, and associate a unique number to these based on the word's/permutation's order of appearance in the dictionary. E.g., words on three characters would be

   perm.              index
    012    <---->       0
    021    <---->       1
    102    <---->       2
    120    <---->       3
    201    <---->       4
    210    <---->       5

You'll see later why it was easiest to use the numbers we did, but others could be accommodated with a bit more work.

To choose one at random, you could pick its associated index randomly from the range 0 ... N!-1 with a uniform probability (the simplest implementation of this is clearly out of the question for even moderately large N, I know, but I think there are decent workarounds) and then determine its associated permutation. Notice that the list begins with all the permutations of the last N-1 elements, keeping the first digit fixed equal to 0. After those possibilities are exhausted, we generate all those that start with 1. After these next (N-1)! permutations are exhausted, we generate those that start with a 2. Etc. Thus we can determine the leading digit is Floor[R / (N-1)!], where R was the index in the sense shown above. See now why we zero indexed, too?

To generate the remaining N-1 digits in the permutation, let's say that we determined Floor[R/(N-1)!] = a0. Start with the list {0, ..., N-1} - {a0} (set subtraction). We want the Qth permutation of this list, for Q = R mod (N-1)!. Except for accounting for the fact that there's a missing digit, this is just the same as the problem we've just solved. Recurse.

Lomalomas