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

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