PHP CookBook

Recipe 4.26 Finding All Permutations of an Array

4.26.1 Problem

You have an array of elements and want to compute all the different ways they can be ordered.

4.26.2 Solution

Use one of the two permutation algorithms discussed next.

4.26.3 Discussion

The pc_permute() function shown in Example 4-6 is a PHP modification of a basic recursive function.

Example 4-6. pc_permute( )

function pc_permute($items, $perms = array( )) {
    if (empty($items)) { 
        print join(' ', $perms) . "\n";
    }  else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             pc_permute($newitems, $newperms);
         }
    }
}

For example:

pc_permute(split(' ', 'she sells seashells'));
she sells seashells
she seashells sells
sells she seashells
sells seashells she
seashells she sells
seashells sells she

However, while this recursion is elegant, it's inefficient, because it's making copies all over the place. Also, it's not easy to modify the function to return the values instead of printing them out without resorting to a global variable.

The pc_next_permutation( ) function shown in Example 4-7, however, is a little slicker. It combines an idea of Mark-Jason Dominus from Perl Cookbook by Tom Christianson and Nathan Torkington (O'Reilly) with an algorithm from Edsger Dijkstra's classic text A Discipline of Programming (Prentice-Hall).

Example 4-7. pc_next_permutation( )

function pc_next_permutation($p, $size) {
    // slide down the array looking for where we're smaller than the next guy
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { }

    // if this doesn't occur, we've finished our permutations
    // the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
    if ($i == -1) { return false; }

    // slide down the array looking for a bigger number than what we found before
    for ($j = $size; $p[$j] <= $p[$i]; --$j) { }

    // swap them
    $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;

    // now reverse the elements in between by swapping the ends
    for (++$i, $j = $size; $i < $j; ++$i, --$j) {
         $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
    }

    return $p;
}

$set = split(' ', 'she sells seashells'); // like array('she', 'sells', 'seashells')
$size = count($set) - 1;
$perm = range(0, $size);
$j = 0;

do { 
     foreach ($perm as $i) { $perms[$j][] = $set[$i]; }
} while ($perm = pc_next_permutation($perm, $size) and ++$j);

foreach ($perms as $p) {
    print join(' ', $p) . "\n";
}

Dominus's idea is that instead of manipulating the array itself, you can create permutations of integers. You then map the repositioned integers back onto the elements of the array to calculate the true permutation — a nifty idea.

However, this technique still has some shortcomings. Most importantly, to us as PHP programmers, it frequently pops, pushes, and splices arrays, something that's very Perl-centric. Next, when calculating the permutation of integers, it goes through a series of steps to come up with each permutation; because it doesn't remember previous permutations, it therefore begins each time from the original permutation. Why redo work if you can help it?

Dijkstra's algorithm solves this by taking a permutation of a series of integers and returning the next largest permutation. The code is optimized based upon that assumption. By starting with the smallest pattern (which is just the integers in ascending order) and working your way upwards, you can scroll through all permutations one at a time, by plugging the previous permutation back into the function to get the next one. There are hardly any swaps, even in the final swap loop in which you flip the tail.

There's a side benefit. Dominus's recipe needs the total number of permutations for a given pattern. Since this is the factorial of the number of elements in the set, that's a potentially expensive calculation, even with memoization. Instead of computing that number, it's faster to return false from pc_next_permutation( ) when you notice that $i == -1. When that occurs, you're forced outside the array, and you've exhausted the permutations for the phrase.

Two final notes of implementation. Since the size of the set is invariant, you capture it once using count( ) and pass it into pc_next_permutation( ); this is faster than repeatedly calling count( ) inside the function. Also, since the set is guaranteed by its construction to have unique elements, i.e., there is one and only one instance of each integer, we don't need to need to check for equality inside the first two for loops. However, you should include them in case you want to use this recipe on other numeric sets, in which duplicates might occur.

4.26.4 See Also

Recipe 4.25 for a function that finds the power set of an array; Recipe 4.19 in the Perl Cookbook (O'Reilly); Chapter 3, A Discipline of Programming (Prentice-Hall).