Cartesian Product of N arrays

Question

I have a PHP array which looks like this example:

$array[0][0] = 'apples';
$array[0][1] = 'pears';
$array[0][2] = 'oranges';

$array[1][0] = 'steve';
$array[1][1] = 'bob';

And I would like to be able to produce from this a table with every possible combination of these, but without repeating any combinations (regardless of their position), so for example this would output

Array 0            Array 1
apples             steve
apples             bob
pears              steve
pears              bob

But I would like for this to be able to work with as many different arrays as possible.

Solution 1

this is called "cartesian product", php man page on arrays http://php.net/manual/en/ref.array.php shows some implementations (in comments).

and here's yet another one:

function array_cartesian() {
    $_ = func_get_args();
    if(count($_) == 0)
        return array(array());
    $a = array_shift($_);
    $c = call_user_func_array(__FUNCTION__, $_);
    $r = array();
    foreach($a as $v)
        foreach($c as $p)
            $r[] = array_merge(array($v), $p);
    return $r;
}

$cross = array_cartesian(
    array('apples', 'pears',  'oranges'),
    array('steve', 'bob')
);

print_r($cross);

Solution 2

You are looking for the cartesian product of the arrays, and there's an example on the php arrays site: http://php.net/manual/en/ref.array.php

Solution 3

Syom copied http://www.php.net/manual/en/ref.array.php#54979 but I adapted it this to become an associative version:

function array_cartesian($arrays) {
  $result = array();
  $keys = array_keys($arrays);
  $reverse_keys = array_reverse($keys);
  $size = intval(count($arrays) > 0);
  foreach ($arrays as $array) {
    $size *= count($array);
  }
  for ($i = 0; $i < $size; $i ++) {
    $result[$i] = array();
    foreach ($keys as $j) {
      $result[$i][$j] = current($arrays[$j]);
    }
    foreach ($reverse_keys as $j) {
      if (next($arrays[$j])) {
        break;
      }
      elseif (isset ($arrays[$j])) {
        reset($arrays[$j]);
      }
    }
  }
  return $result;
}

Solution 4

I needed to do the same and I tried the previous solutions posted here but could not make them work. I got a sample from this clever guy http://www.php.net/manual/en/ref.array.php#54979. However, his sample did not managed the concept of no repeating combinations. So I included that part. Here is my modified version, hope it helps:

$data = array(
        array('apples', 'pears',  'oranges'),
        array('steve', 'bob')
    );

    $res_matrix = $this->array_cartesian_product( $data );

    foreach ( $res_matrix as $res_array )
    {
        foreach ( $res_array as $res )
        {
            echo $res . " - ";
        }
        echo "<br/>";
    }


function array_cartesian_product( $arrays )
{
    $result = array();
    $arrays = array_values( $arrays );

    $sizeIn = sizeof( $arrays );
    $size = $sizeIn > 0 ? 1 : 0;
    foreach ($arrays as $array)
        $size = $size * sizeof( $array );
    $res_index = 0;
    for ( $i = 0; $i < $size; $i++ )
    {
        $is_duplicate = false;
        $curr_values  = array();
        for ( $j = 0; $j < $sizeIn; $j++ )
        {
            $curr = current( $arrays[$j] );
            if ( !in_array( $curr, $curr_values ) )
            {
                array_push( $curr_values , $curr ); 
            }
            else
            {
                $is_duplicate = true;
                break;
            }
        }
        if ( !$is_duplicate )
        {
            $result[ $res_index ] = $curr_values;
            $res_index++;
        }
        for ( $j = ( $sizeIn -1 ); $j >= 0; $j-- )
        {
            $next = next( $arrays[ $j ] );
            if ( $next )
            {
                break;
            }
            elseif ( isset ( $arrays[ $j ] ) )
            {
                reset( $arrays[ $j ] );
            }
        }
    }
    return $result;
}

The result would be something like this:
apples - steve
apples - bob
pears - steve
pears - bob
oranges - steve
oranges - bob

If you the data array is something like this:

  $data = array(
        array('Amazing', 'Wonderful'),
        array('benefit', 'offer', 'reward'),
        array('Amazing', 'Wonderful')
    );

Then it will print something like this:

Amazing - benefit - Wonderful
Amazing - offer - Wonderful
Amazing - reward - Wonderful
Wonderful - benefit - Amazing
Wonderful - offer - Amazing
Wonderful - reward - Amazing

Solution 5

foreach($parentArray as $value) {
    foreach($subArray as $value2) {
        $comboArray[] = array($value, $value2); 
    }
}

Don't judge me..

View more solutions

Comments

[Nanne]

If this function lives in a class, you might want to change the user_func call like so: $c = call_user_func_array(array($this,__FUNCTION__), $_);. Also, it can give a warning (not an array) if input-arrays aren't of equal size.

[Walf]

This is a good solution but the result of the first short circuit is truthy, which does not make sense to me. Try this one.