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:

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:

And keep the algorithm like this:

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:

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

You may be also interested in…

0 comentarios

¿Me dejas un comentario? ¡Gracias!

Deja un comentario

Los campos obligatorios están marcados con *