CombinationGenerator example

CombinationGenerator.Php

<?php

class CombinationGenerator implements \Iterator
{
    private $array;
    private $length;
    private $itemCount;
    private $pos = -1;
    private $binArray = array();
    private $cache = array();

    function __construct(array $array, $length = 0) {
        $this->array = $array;
        $this->itemCount = count($array);
        $this->length = $length;

        if($length > $this->itemCount) {
            throw new \Exception("Cannot pick $length item from $this->itemCount");
        }

        $this->init();

    }
    private function init() {
        $this->buildBinaryArray();
        $this->rewind();
    }

    private function buildBinaryArray() {

        $binaryString = str_repeat(1, $this->itemCount);
        $max = bindec($binaryString);

        for ($i = $max; $i > 0; $i--)
        {
            if (substr_count(decbin($i), "1") == $this->length)
            {
                $this->binArray[] = str_split(str_pad(decbin($i), $this->itemCount, "0", STR_PAD_LEFT));
            }
        }
    }

    function key() {
        return $this->pos;
    }

    function current()
    {
        if (!isset($this->binArray[$this->pos])) {
            return null;
        }

        if(!isset($this->cache[$this->pos])){
            $this->createCache();
        }

        return $this->cache[$this->pos];

    }

    function next() {
        $this->pos++;
    }

    function rewind() {
        $this->pos = 0;
    }

    function valid() {
        return isset($this->binArray[$this->pos]);
    }

    private function createCache()
    {
        $this->cache[$this->pos] = array();

        foreach ($this->binArray[$this->pos] as $indx => $digit) {
            if ($digit == '1') {
                $this->cache[$this->pos][] = $this->array[$indx];
            }
        }
    }

}

class MaxSumFilterIterator extends \FilterIterator
{
    private $maxSum = 0;

    public function __construct(Iterator $iterator , $maxSum )
    {
        parent::__construct($iterator);
        $this->maxSum = $maxSum;
    }

    public function accept()
    {
        $array = $this->getInnerIterator()->current();

        return (array_sum($array)) <= $this->maxSum;
    }
}

//Usages
$array = ['1', '2', '3', '4', '5', '6', '7'];

$allCombinations = new CombinationGenerator($array, 5);

foreach($allCombinations as $key => $subSet){
    echo ' ----- ' . $key . PHP_EOL;
    print_r($subSet);
}

$combinationWithMaxSum = new MaxSumFilterIterator($allCombinations, 16);

foreach($combinationWithMaxSum as $key => $subSet){
    echo ' ----- ' . $key . PHP_EOL;
    print_r($subSet);
}