PHP Cookbook

4.25. Finding All Permutations of an Array

Problem

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

Solution

Use one of the two permutation algorithms discussed next.

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 ...