Page 1 of 1
all combinations of an array
Posted: Sat Aug 08, 2009 7:06 am
by f_jones
Hi gurus,
i've been googling for this problem but couldn't find any solution. I want to create a multidimensional array from a normal array which includes all combinations of the given array. Example:
Code: Select all
$arr = Array(0, 1, 2, 3);
/*and you get*/
$arr2 = Array(Array(0), Array(1 ... Array(0, 1, 2, 3));
I am using currently the following function for this job:
Code: Select all
private function pc_array_power_set($array) {
$results = array(array( ));
foreach ($array as $element){
foreach ($results as $combination){
array_push($results, array_merge(array($element), $combination));
}
}
return $results;
}
/*and iterate the returned array to filter arrays in certain size*/
foreach($result as $v){
if(count($v) == $size){
/*put them in another array*/
}
}
This function works fine but i run out of memory if the given array is long. So my question is, how can i manipulate this function to get the combination arrays in certain size so other sub arrays are never created. And i hope i can handle the memory issue this way.
Example:
Code: Select all
$given_array = Array(0, 1, 2);
$return_array = Array(Array(0, 1), Array(0, 2), Array(1, 2));
Thanks in advance.
Re: all combinations of an array
Posted: Sat Aug 08, 2009 9:48 am
by prometheuzz
Edit: wait, I see what you mean. Never mind my previous questions.
Re: all combinations of an array
Posted: Sat Aug 08, 2009 1:02 pm
by prometheuzz
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!
Re: all combinations of an array
Posted: Sun Aug 09, 2009 4:20 am
by f_jones
Well thank you very much for your help, it did exactly the job. I wish i could understand how your code works. I don't have any idea how an interface can help with such a problem. I guess, you overwrite the core functions of the array object or loop logic by implementing the interface so loops behaves different. Is this correct

I am very grateful, thaks again.
Re: all combinations of an array
Posted: Sun Aug 09, 2009 5:03 am
by prometheuzz
f_jones wrote:Well thank you very much for your help, it did exactly the job. I wish i could understand how your code works. I don't have any idea how an interface can help with such a problem. I guess, you overwrite the core functions of the array object or loop logic by implementing the interface so loops behaves different. Is this correct

I am very grateful, thaks again.
You're welcome.
In OOP (Object Oriented Programming) an interface defines some sort of contract. I know this will sound a bit vague, but here's a good tutorial on all these kind of OOP concepts:
http://java.sun.com/docs/books/tutorial/java/concepts/
Note that although the tutorial focusses on Java, the concepts are similar to PHP's OOP features. I just don't know a PHP tutorial that's as good as the Java version I posted. Not because there aren't any good tutorials about it in PHP, but because I am not familiar with PHP.
Of course, you can have a look at the official PHP documentation on the Iterator interface:
http://us2.php.net/manual/en/class.iterator.php
Good luck.