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.
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).
Get PHP Cookbook now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.