Announcing Stack Overflow Documentation



Sign up and start helping → Learn more about Documentation →

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.

share|improve this question
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? – Wizetux Nov 7 '11 at 23:45
It would, that's why I said the elements are` 1..N`, so that they need not to be passed as an input vector. – eold Nov 7 '11 at 23:55
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; – Bruno Reis Nov 8 '11 at 4:36

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.

share|improve this answer
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? – eold Nov 8 '11 at 1:10
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). – comingstorm Nov 8 '11 at 18:36
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. – comingstorm Nov 8 '11 at 18:43

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.

share|improve this answer
That bound is essentially tight because there's a generator that uses n + O(log n) bits. – not for show Nov 7 '11 at 23:56
Good point. But what if I am interested in a random permutation, with uniform probability distribution? – eold Nov 8 '11 at 1:11

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;
    if (i == last) return false; // False for single-element ranges.
    i = last;
    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?

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer


