Okay, so you're looking for a way to generate all k-combinations from a set (or list) of n-elements.
You could utilize PHP's OOP-capability here by implementing the Iterator interface. That way you don't need to store all combinations but cycle through them as you need them.
Code: Select all
class KCombinations implements Iterator {
private $values;
private $n;
private $k;
private $combination_number;
private $total_combinations;
private $currentIndices;
public function __construct($values, $k) {
$this->values = array_values($values);
$this->n = sizeof($values);
$this->k = $k;
$this->total_combinations = $this->fac($this->n) /
($this->fac($this->k) * $this->fac($this->n - $this->k));
$this->rewind();
}
function rewind() {
$this->combination_number = 1;
$this->currentIndices = array();
for($i = 0; $i < $this->k; $i++) {
$this->currentIndices[] = $i;
}
}
function current() {
$combination = array();
foreach($this->currentIndices as $index) {
$combination[] = $this->values[$index];
}
return $combination;
}
function fac($n) {
$f = 1;
for($i = 2; $i <= $n; $i++) {
$f *= $i;
}
return $f;
}
function key() {
return $this->combination_number;
}
function next() {
$this->combination_number++;
for($i = $this->k-1, $j = $this->n-1; $i >= 0; $i--, $j--) {
if($this->currentIndices[$i] != $j) {
$this->currentIndices[$i]++;
for($p = $i+1; $p < $this->k; $p++) {
$this->currentIndices[$p] = $this->currentIndices[$p-1]+1;
}
return;
}
}
}
function valid() {
return $this->combination_number <= $this->total_combinations;
}
}
$combinations = new KCombinations(array(4,5,6,7,8), 3);
foreach($combinations as $combNumber => $comb) {
echo "combination[$combNumber] -> ";
foreach($comb as $c) {
echo "$c ";
}
echo "\n";
}
Note that the implementation above can easily be broken by providing incorrect arguments, but I leave that for you to fix.
When executing the script above, this is the output:
Code: Select all
combination[1] -> 4 5 6
combination[2] -> 4 5 7
combination[3] -> 4 5 8
combination[4] -> 4 6 7
combination[5] -> 4 6 8
combination[6] -> 4 7 8
combination[7] -> 5 6 7
combination[8] -> 5 6 8
combination[9] -> 5 7 8
combination[10] -> 6 7 8
More information on the algorithm can be found on:
http://big-o.nl/demos/math/combinationg ... index.html
Good luck!