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[0], 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[0], 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.
     *
     * @link https://en.wikipedia.org/wiki/Heap%27s_algorithm
     *
     * @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);
                }
            }
        }
    }
}

Thanks for reading this post, I hope it will be helpful.

You may be also interested in…