Finding permutations with Heap algorithm in PHP

Created:26 Oct 2017 16:54:32 , in  Maths

Suppose, you are given a list of two items, say one is called "a" and the other "b" and asked to find all the possible arrangements (also called permutations without repetition) of these items. All your arrangements should consist of exactly the number of items in the list (two for this case) and none of them should contain two similar items. One answer to this puzzle is: ("a","b"),("b","a"). Nothing hard here.

Now suppose, you get a list of just one item, say "a". For such a case, the only permutation I can think of is ("a"). Generally, number of permutations of a set of n items is given by n! (n factorial). Using this fact, for a list with three items, there are 6 arrangements, for four items there are 24 of them, and so on.

Although, finding 6 permutations is tolerable, I certainly would have to be hard-pressed to look for 24 of them by hand.

Fortunately, obtaining 6 arrangements from a list of 3 items is sufficient to test a computer program which can find permutations from much larger lists. How is it possible?

Permutations of n items in a list can be found in a consistent manner through interchanges of positions of those items in the list. "A consistent manner" hints at an underlying pattern. In Maths, if there is a pattern you often use recursion to explore it beyond the most basic cases.

In 1963 B.R. Heap proposed a very efficient algorithm for finding permutations without repetition of n items in the list. The algorithm is a recursive one. Like many other recursive algorithms it looks deceptively simple. However, tracking what it does is frequently far from simple. Perhaps you should try it for yourself. If you would like to visualise what you are doing a 2-permutahedron embedded in 3-dimensional space as a model might prove very useful to you.

Heap algorithm implementation in PHP

Moving on to making Heap algorithm work for you, below is my object oriented implementation of it in PHP programming language.

/*
  Class: SWWWPermutations 
  Description: Find permutations of n items using Heap algorithm
  Author: Sylwester Wojnowski
  WWW: wojnowski.net.pl

  Methods:
    generate($A) - public static - generate permutations
      parameters:
        $A - array - list of items to permute
        return - array - list of lists of permutations 
*/
class SWWWPermutations{
  private $B = array();

  /*
    generate permutations of items in the list 
  */
  public static function generate($A){
    $instance = new SWWWPermutations($A);
    return $instance -> get();
  }
  
  public function __construct($A){
    $n = count($A);
    self::Heap($n,$A);
  }
  
  /* 
    swap function used by Heap routine
  */
  private static function swap(&$x,&$y) {
    list($x,$y) = array($y,$x);
  }
  
  /* 
    (slightly extended) Heap algorithm for find permutations of items in list A
  */  
  private function Heap($n,&$A){
    if ($n <= 0) {
      $this -> B[] = array();
      return $A;
    }
    
    if ($n === 1) {
      $this -> B[] = $A;
      return $A;
    }
    
    for ($i = 0; $i < $n - 1; $i++) {
      $this -> Heap($n - 1, $A);
      ($n % 2) === 0 ? $this -> swap($A[$i],$A[$n-1]) : $this -> swap($A[0],$A[$n-1]); 
    }
    $this -> Heap($n - 1,$A);
  }
  
  public function get(){
    return $this -> B;
  }
}

It is worth noting, that Class SWWWPermutations uses indices exclusively to move items over in the input array. It is not aware of type of items it interchanges. Hence they can be numbers, strings, arrays or whatever else one can store in the PHP array. See the second use example below.

Examples of use

Finding permutations of 3 items:

$C = array('x','y','z');
SWWWPermutations::generate($C);

/*
=>
array(
  array('x','y','z'),
  array('y','x','z'),
  array('z','x','y'),
  array('x','z','y'),
  array('y','z','x'),
  array('z','y','x')
);
*/

Finding permutations of a list of associative arrays (2 items for simplicity):

$D = array( 
   array(
     'color' => 'yellow'  
   ),
   array(
     'color' => 'green'
   ),
);

SWWWPermutations::generate($D);

/*
=>    
array(
  array(
    array(
      'color' => 'yellow'  
    ),
    array(
      'color' => 'green'
    )
  ),
  array(
    array(
      'color' => 'green'
    ),
    array(
      'color' => 'yellow'  
    )
  )
); 
*/

Conclusion

Finding permutations of more than 3, 4 items, is a hardly suitable task for humans to perform. Number of arrangements obtainable from a set consisting of 10 items is 3 628 800, a number sufficient to keep many modern computers really busy for a short while, let alone humans.

Ubiquitousness of permutations in Maths and other disciplines, means they have to be computed, and computed often, though. Efficient algorithms, like Heap algorithm mentioned here, are invaluable to complete this arduous task.

Heap algorithm was discovered about 50 years ago. Nonetheless, it remains one of the best tools for finding permutations without repetition ever devised. I hope, my implementation of it will prove useful.

This post was updated on 26 Oct 2017 21:25:48

Tags:  combinatorics ,  php