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

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.

- Generating permutations with Heap’s algorithm
- Heaps algorithm in C++ repeating?
- Heap’s algorithm permutation generator
- No repeats please, Heap’s algorithm and frustration with recursions

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.