How to generate combinations of the elements in several arrays?

Question

Hi,

This is my first question here :)

I have an array with a number of array children, each with unique values and would like to get all the possible unique combinations of those values.

The number of arrays is known but may change over time.

For example,

array(
  [0] => array([0]=>'blue',[1]=>'red'),
  [1] => array([0]=>'sunny',[1]=>'cloudy'),
  [2] => array([0]=>'sweet',[1]=>'acid');

What should I do to get:

array(
  [0] => array([0]=>'blue',[1]=>'sunny',[2]=>'sweet'),
  [1] => array([0]=>'blue',[1]=>'sunny',[2]=>'acid'),
  [2] => array([0]=>'blue',[1]=>'cloudy',[2]=>'sweet'),
  [3] => array([0]=>'blue',[1]=>'cloudy',[2]=>'acid'),
  [4] => array([0]=>'red',[1]=>'sunny',[2]=>'sweet'),
  [5] => array([0]=>'red',[1]=>'sunny',[2]=>'acid'),
  [6] => array([0]=>'red',[1]=>'cloudy',[2]=>'sweet'),
  [7] => array([0]=>'red',[1]=>'cloudy',[2]=>'acid'));

I've tried doing it with nested loops but my logic is not too strong.

Very much appreciated if someone can shed some light

Answer 1

(Note: needs a slight modification to use in PHP < 5.3)

Do this (example on an online interpreter):

$f = function () { return func_get_args(); };
$res = array_outer($f,
    array("blue", "red"),
    array("sunny", "cloudy"),
    array("sweet", "acid"));

The function array_outer, inspired in Mathematica's Outer, is this:

/**
 * A generalization of the outer product, forming all the possible
 * combinations of the elements of any number of arrays and feeding
 * them to $f.
 * The keys are disregarded
 **/
function array_outer($f, array $array1) {
    $res = array();
    $arrays = func_get_args();
    array_shift($arrays);
    foreach ($arrays as $a) {
        if (empty($a))
            return $res;
    }

    $num_arrays = count($arrays);
    $pos = array_fill(0, $num_arrays, 0);
    while (true) {
        $cur = array();
        for ($i = 0; $i < $num_arrays; $i++) {
            $cur[] = $arrays[$i][$pos[$i]];
        }
        $res[] = call_user_func_array($f, $cur);
        for ($i = $num_arrays-1; $i >= 0; $i--) {
            if ($pos[$i] < count($arrays[$i]) - 1) {
                $pos[$i]++;
                break;
            } else {
                if ($i == 0)
                    break 2;
                $pos[$i] = 0;
            }
        }
    }
    return $res;
}

Answer 2

latenight pseudocode:

result = []
counter = 0
for i in length(array[0]):
  for j in length(array[1]):
    for k in length(array[2]):      
      result[counter] = aray(0: array[0][i], 1: array[1][j], 2: array[2][k])
      counter+=1

although a strong point might be made for a recursive approach if the number of arrays is going to get bigger or may change dynamically

Answer 3

Here's a recursive approach to this:

$arr =  array(
            0 => array(0 =>'blue', 1 =>'red'),
            1 => array(0 =>'sunny', 1 =>'cloudy'),
            2 => array(0 =>'sweet', 1 =>'acid')
        );

$combinations = array();
getArrayCombinations($arr, $combinations);
echo '<pre>';print_r($combinations);

/**
 * Creates an array with all possible combinations
 * @param array main_array - Array to find all the possible combinations of
 * @param array combinations - Array to store the resulting array in
 * @param array batch
 * @param int index
 */
function getArrayCombinations($main_array, &$combinations, $batch=array(), $index=0)
{
    if ($index >= count($main_array))
        array_push($combinations, $batch);
    else
        foreach ($main_array[$index] as $element)
        {
            $temp_array = $batch; array_push($temp_array, $element);
            getArrayCombinations($main_array, $combinations, $temp_array, $index+1);
        }
}

Answer 4

What you're really looking for is a way to iterate sequences:

000
001
010
011
100
101
110
111

It would be nice too if we didn't have to make the assumption that the size of each input array is the same. So if we decrease the size of the second array by 1:

array(
  [0] => array([0]=>'blue',[1]=>'red'),
  [1] => array([0]=>'sunny'),
  [2] => array([0]=>'sweet',[1]=>'acid');

...we want the maximum value for that column to decrease by 1:

000
001
100
101

This abstraction makes the problem easier to think about. How would you iterate this sequence? On each iteration, you increase the rightmost column by 1. If doing so would increase it beyond its maximum, reset it 0 and move left a column. Now you repeat what you just did on the last column. If you can't increase this column either, reset it to 0, move left, rinse, and repeat. If you move all the way across and haven't been able to increase any column without going beyond its maximum, you're done.

We can wrap the above logic in a PHP iterator:

class Sequence implements Iterator {

    private $input;

    private $hasNext;
    private $positions;

    public function __construct(array $input) {
        $this->input = $input;
    }

    public function rewind() {
        $this->hasNext = true;
        $this->positions = array();
        for ($i = 0; $i < count($this->input); $i++) {
            $this->positions[$i] = 0;
        }
    }

    public function valid() {
        return $this->hasNext;
    }

    public function current() {
        $current = array();
        for ($i = 0; $i < count($this->positions); $i++) {
            $current[] = $this->input[$i][$this->positions[$i]];
        }
        return $current;
    }

    public function key() {}

    public function next() {
        for ($i = count($this->positions) - 1; $i >= 0; $i--) {
            if ($this->positions[$i] < count($this->input[$i]) - 1) {
                $this->positions[$i]++;
                break;
            } else {
                $this->positions[$i] = 0;
                $this->hasNext = $i !== 0;
            }
        }
    }

}

next() is the implementation of the above logic. reset() simply sets each column back to 0 and current() uses the current sequence as the indexes of the input to return the current values.

Here it is in action (with "cloudy" removed to show the generality of the solution):

$input = array(
    array('blue', 'red'),
    array('sunny'),
    array('sweet', 'acid')
);

$lst = new Sequence($input);
foreach ($lst as $elt) {
    print(implode(', ', $elt) . "\n");
}

And its output:

blue, sunny, sweet
blue, sunny, acid
red, sunny, sweet
red, sunny, acid