all combinations of an array

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
f_jones
Forum Newbie
Posts: 2
Joined: Sat Aug 08, 2009 6:53 am

all combinations of an array

Post 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.
User avatar
prometheuzz
Forum Regular
Posts: 779
Joined: Fri Apr 04, 2008 5:51 am

Re: all combinations of an array

Post by prometheuzz »

Edit: wait, I see what you mean. Never mind my previous questions.
User avatar
prometheuzz
Forum Regular
Posts: 779
Joined: Fri Apr 04, 2008 5:51 am

Re: all combinations of an array

Post 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!
Last edited by prometheuzz on Sun Aug 09, 2009 4:47 am, edited 2 times in total.
f_jones
Forum Newbie
Posts: 2
Joined: Sat Aug 08, 2009 6:53 am

Re: all combinations of an array

Post 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.
User avatar
prometheuzz
Forum Regular
Posts: 779
Joined: Fri Apr 04, 2008 5:51 am

Re: all combinations of an array

Post 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.
Post Reply