Permutation algorithm of N unique elements with low memory footprint

Question

I actually had a real life need (outside work, no less) to come up with every single permutation of N elements (the N in my case being 12, so a total of 12! = 479,001,600) and run each one against a simple evaluation to produce some metric in order to determine which permutation is the most optimal.

Since I have some background in combinatorics, in addition to software development, I thought this would be relatively simple but it proved not to be if I am to avoid recursion, which seems elegant for low Ns but grows monstrously memory heavy and inefficient at higher Ns, even as low as 10.

In addition, recursion and generally combining set elements with index positions by brute force of cartesian product seems like a memory intensive and sort of crude and less sophisticated way of doing it. By observing manually assembled permutations of smaller sets (notably 3 elements), I noticed there must be a pattern to perform a simple swap of elements from the last permutation to come up with the next without ever needing to consider any previous permutation, which effectively reduces the memory footprint of this operation to only two lists of N elements while the recursion based approach linked above was storing a huge amounts of permutated subsets in memory data structures. As an aside, I like my approach better because it is easier to read and follow the code than the recursive approach.

The algorithm my Java method follows is exactly as laid out in the accepted answer:

static void getPermutations(int size) {

    TreeSet<Integer> origSet = new TreeSet<Integer>();

    for(int i = 0; i < size; i++) {
        origSet.add(i);
    }

    List<Integer> activePerm = new ArrayList<Integer>(origSet);

    System.out.println(">>> Permutation generation start:\n");

    int permCntr = 0;

    boolean hasMore = true;

    long timeMilliStart = (new Date()).getTime();

    while(hasMore) {

        permCntr++;
        System.out.println(permCntr + ". " + activePerm);

        TreeSet<Integer> activeSet = new TreeSet<Integer>(origSet);

        for(int i = size; i > 0;) {

            i--;
            Integer elem = activePerm.get(i);

            if(i > 0) {

                int prevIndx = i - 1;
                Integer prevElem = activePerm.get(prevIndx);

                if(prevElem < elem) {

                    List<Integer> newPerm = new ArrayList<Integer>();

                    for(int j = 0; j < prevIndx; j++) {
                        Integer keeper = activePerm.get(j);
                        activeSet.remove(keeper);
                        newPerm.add(keeper);
                    }

                    Integer incr = prevElem + 1;

                    while(!activeSet.contains(incr)) {
                        incr++;
                    }

                    activeSet.remove(incr);
                    newPerm.add(incr);

                    newPerm.addAll(activeSet);

                    activePerm = newPerm; 

                    i = 0;
                }
            } else {
                hasMore = false;
            }
        }
    }

    long timeMilliEnd = (new Date()).getTime();
    long procMillis = timeMilliEnd - timeMilliStart;
    float procSecs = (float)procMillis / 1000f;

    System.out.println("\n>>> Process time (secs): " + procSecs);
}

The key to sparing memory is that my approach relies on not needing to store the generated permutations in some data structure for post processing but to use each permutation in the loop iteration when it is generated and then have it garbage collected, which is what I was using for the optimization evaluation described in the first paragraph, which is not included in the code above because it is not germane to the core problem of permutations.

Difference in performance can be seen if you try to run my method against a set of 10 elements. At 11 elements (39,916,800 permutations), his program causes an out of memory exception on my laptop, which has a duo CPU at 2.54GHz and 6G of RAM, while mine runs smoothly in several minutes.

Answer 1

Recursion not bad

I'm not sure why you think recursion is bad. The maximum depth of recursion is going to be N, so given your likely case of N = 12, you will only be using 12 stack levels. As long as you don't create temporary copies of the array, you will barely use any extra memory at all.

Heap's algorithm

I suspect your algorithm is equivalent to an iterative version of Heap's algorithm. But the recursive version is more compact:

static void getPermutations(int size) {
    int [] array = new int[size];

    for (int i = 0; i < size; i++) {
        array[i] = i;
    }
    generatePermutations(size, array);
}

static void generatePermutations(int n, int [] array)
{
    if (n == 1) {
        System.out.println(Arrays.toString(array));
        return;
    }
    for (int i = 0; i < n; i++) {
        generatePermutations(n - 1, array);
        if ((n & 1) == 0) {
            int tmp = array[i];
            array[i]   = array[n-1];
            array[n-1] = tmp;
        } else {
            int tmp = array[0];
            array[0]   = array[n-1];
            array[n-1] = tmp;
        }
    }
}

I coded this straight out of the Wikipedia article for Heap's algorithm. It ran about 1.7x faster than your iterative version. Notice it doesn't use any additional memory because it doesn't make any copies of the array.

Alternative iterative solution

Here is an easier to understand solution that uses iteration instead of recursion. It basically takes a permutation number (from 0 to n! - 1) and constructs a permutation based on that number. It runs about as fast as the recursive solution.

static void getPermutations(int size) {
    int [] array        = new int[size];
    int [] factorials   = new int[size];
    int numPermutations = factorial(size);

    for (int i=0;i<size;i++)
        factorials[i] = factorial(size-1-i);

    for (int i = 0; i < numPermutations; i++) {
        int combination      = i;
        int remainingBitmask = (1 << size) - 1;

        for (int j = 0; j < size; j++) {
            // WhichNumber tells us which of the remaining numbers we
            // should pick.  For example, if whichNumber is 4 and the
            // numbers left are { 0, 3, 4, 6, 9, 10 }, it will pick the
            // 4th number which is 9.
            int whichNumber = combination / factorials[j];
            combination %= factorials[j];

            // The remainingBitmask tells us which numbers are left to
            // choose from.  For example, if { 0, 3, 4, 6, 9, 10 } are
            // remaining, then remainingBitmask will be 0x659, which
            // are bits 0, 3, 4, 6, 9, and 10 set.  The expression
            // "bits -= (bits & -bits)" strips the rightmost bit.
            int bits = remainingBitmask;
            while (whichNumber > 0) {
                bits -= (bits & -bits);
                whichNumber--;
            }

            // At this point, the rightmost bit signifies the number we
            // are looking for.  We put that into the array and remove
            // that number from remainingBitmask.
            int nextNum = Integer.numberOfTrailingZeros(bits);
            remainingBitmask &= ~(1 << nextNum);
            array[j] = nextNum;
        }
        System.out.println(Arrays.toString(array));
    }
}

The big advantage of this solution is that you can easily modify this to be multithreaded, because the main part of the function can decode any permutation number you give it. So you could divide your permutations among multiple threads if you wanted to.