Heap’s Algorithm Implementation in PHP

Have you ever needed to compute all permutations of a set of elements? I’m sure you have, and that’s why you’re googling for this today! Aren’t you? Please keep on reading. I’m posting a PHP implementation of Heap’s algorithm that works OK.

Permutations, you know. For instance, you may want to count how many arrangements can be made from a few pool balls, or it turns out that you need to know how many English words can be made with the letters ELOHL. The list of useful examples for which permutations are required goes on and on… This is a permutation!

In such scenarios, you’ll probably do some research and conclude that the best thing to do is rely on Heap’s algorithm. Then, you’re likely to transcribe Wikipedia’s pseudocode into the programming language of your choice — PHP, Python, Java, C++, Ruby, JavaScript or whatever – only to realize there’s something wrong in your code. Your Heap’s implementation generates repeated permutations, removes a few, or whatever unexpected thing. Sound familiar?

Something’s not working as expected.

By the way, here’s Wikipedia’s pseudocode:

```procedure generate(n : integer, A : array of any):
if n = 1 then
output(A)
else
for i := 0; i < n - 1; i += 1 do
generate(n - 1, A)
if n is even then
swap(A[i], A[n-1])
else
swap(A, A[n-1])
end if
end for
generate(n - 1, A)
end if
```

Welcome to the Club of Heap’s Algorithms That Fail

Don’t panic, you’re not the only one. My first and second attempts were wrong too, my code was repeating elements unexpectedly. Then, after doing some research on the issue I came across the following resources which helped me understand what was going on.

Fortunately enough I could fix the problem.

Here’s My Own PHP Recursive Implementation

In a nutshell, the recursive variant of Wikipedia’s pseudocode is wrong. Just get rid of the second call to the `generate` function:

```generate(n - 1, A)
```

And keep the algorithm like this:

```procedure generate(n : integer, A : array of any):
if n = 1 then
output(A)
else
for i := 0; i < n; i += 1 do
generate(n - 1, A)
if n is even then
swap(A, A[n-1])
else
swap(A[i], A[n-1])
end if
end for
end if
```

Note how the for loop is been modified as well. On the other hand, keep in mind that the array of items is actually modified on the fly, which means that it needs to be passed by reference, not by value. Well, without any further delay, here’s how my PHP code looks like within the context of an object-oriented class:

```/**
* Permutation.
*/
class Permutation
{
/**
* @var array
*/
protected \$items;

/**
* @var array
*/
protected \$result = [];

/**
* Constructor.
*
* @param array \$items
*/
public function __construct(\$items)
{
\$this->setItems(\$items)->heaps(\$this->n, \$this->items);
sort(\$this->result);
}

/**
* Get items.
*
* @return array
*/
public function getItems()
{
return \$this->items;
}

/**
* Get result.
*
* @return array
*/
public function getResult()
{
return \$this->result;
}

/**
* Set items.
*
* @param array \$items
*/
public function setItems(\$items)
{
\$this->items = \$items;
\$this->n = count(\$items);

return \$this;
}

private function swap(&\$items, \$i, \$j)
{
\$temp = \$items[\$i];
\$items[\$i] = \$items[\$j];
\$items[\$j] = \$temp;
}

/**
* This is Heap's algorithm, generates all possible permutations of n items.
*
*
* @param int   \$n
* @param array \$items
*/
private function heaps(\$n, &\$items)
{
if (\$n == 1) {
\$this->result[] = implode('', \$items);
} else {
for (\$i = 0; \$i < \$n; ++\$i) {
\$this->heaps(\$n - 1, \$items);
if (\$n % 2 == 0) {
\$this->swap(\$items, 0, \$n - 1);
} else {
\$this->swap(\$items, \$i, \$n - 1);
}
}
}
}
}
```