generating combinations in php

10 September 2007 // php. stuff.

This is just a follow-up to the previous post, describes how to enumerate combinations using php iterators.

The code is based on the same principle as the previous one. Combinations($subject, $k) generates all k-combinations of subject (which can be array or string) in lexicographical order.

foreach(new Combinations("ABCD", 2) as $substring)
    echo $substring, ' ';

prints

AB AC AD BC BD CD

$fruits = array('apple', 'banana', 'orange', 'pear');
foreach(new Combinations($fruits, 3) as $k => $v)
    echo $k + 1, ' ', implode(',', $v), " \n";

prints

1 apple,banana,orange
2 apple,banana,pear
3 apple,orange,pear
4 banana,orange,pear

The code is partially based on the java one found here.

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

    function __construct($s, $k) {
        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->k = $k;
        $this->rewind();
    }
    function key() {
        return $this->pos;
    }
    function current() {
        $r = array();
        for($i = 0; $i < $this->k; $i++)
            $r[] = $this->s[$this->c[$i]];
        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->k);
        $this->pos = 0;
    }
    function valid() {
        return $this->pos >= 0;
    }
    //
    protected function _next() {
        $i = $this->k - 1;
        while ($i >= 0 && $this->c[$i] == $this->n - $this->k + $i)
            $i--;
        if($i < 0)
            return false;
        $this->c[$i]++;
        while($i++ < $this->k - 1)
            $this->c[$i] = $this->c[$i - 1] + 1;
        return true;
    }
}