generating permutations in php

16 August 2007 // php. stuff.

Generating permutations (all possible combinations) of characters or array elements is asked often in php groups. Although simple, the answer is relatively verbose, so I thought I post it here for later reference.

function next_permutation(&$a) {
    $n = count($a);
    for($i = $n - 2; $a[$i] > $a[$i + 1]; $i--)
        if(!$i) return false;
    for($j = $n - 1; $a[$i] > $a[$j]; $j--);
    $q = $a[$j]; $a[$j] = $a[$i]; $a[$i] = $q;
    while(++$i < --$n) {
        $q = $a[$n]; $a[$n] = $a[$i]; $a[$i] = $q;
    }
    return true;
}

This code generates permutations in a "lexicographical" (alphabetical) order. We start with the sorted array of numbers and repeat until array is reverse sorted:

$a = array(1, 2, 3);
$k = 0;
do {
    echo ++$k, '. ', implode('', $a), " <br> \n";
} while(next_permutation($a));

1. 123
2. 132
3. 213
4. 231
5. 312
6. 321

This works ok, but not good enough: first, it's limited to integer arrays, we'd like it to work with arbitrary arrays and strings, and second, do...while is certainly not the best way to loop, we want the "natural" php way, i.e. foreach. Fortunately, there is the Iterator interface in php5, we can utilize it to make our "API" as simple as

foreach(new Permutations("ABC") as $k => $v)
    echo $v, " <br> \n";

or

$fruits = array('apple', 'banana', 'orange');
foreach(new Permutations($fruits) as $k => $v)
    echo implode(' ', $v), " <br> \n";

The code is as follows:

class Permutations implements Iterator
{
    protected $c = null;
    protected $s = null;
    protected $n = 0;
    protected $pos = 0;

    function __construct($s) {
        if(is_array($s)) {
            $this->s = array_values($s);
            $this->n = count($this->s);
        } else {
            $this->s = (string) $s;
            $this->n = strlen($this->s);
        }
        $this->rewind();
    }
    function key() {
        return $this->pos;
    }
    function current() {
        $r = array();
        foreach($this->c as $k)
            $r[] = $this->s[$k];
        return is_array($this->s) ? $r : implode('', $r);
    }
    function next() {
        if($this->_next())
            $this->pos++;
        else
            $this->pos = -1;
    }
    function rewind() {
        $this->c = range(0, $this->n - 1);
        $this->pos = 0;
    }
    function valid() {
        return $this->pos >= 0;
    }
    //
    protected function _next() {
        $n = count($this->c);
        if($n == 1) return false;
        for($i = $n - 2; $this->c[$i] > $this->c[$i + 1]; $i--)
            if(!$i) return false;
        for($j = $n - 1; $this->c[$i] > $this->c[$j]; $j--);
        $q = $this->c[$j];
        $this->c[$j] = $this->c[$i];
        $this->c[$i] = $q;
        while(++$i < --$n) {
            $q = $this->c[$n];
            $this->c[$n] = $this->c[$i];
            $this->c[$i] = $q;
        }
        return true;
    }
}