Reputation: 613

How to generate in PHP all combinations of items in multiple arrays

I'im trying to find all combinations of items in several arrays. The number of arrays is random (this can be 2, 3, 4, 5...). The number of elements in each array is random too...

For exemple, I have the 3 arrays :

$arrayA = array('A1','A2','A3');
$arrayB = array('B1','B2','B3');
$arrayC = array('C1','C2');

I would like to generate an array with 3 x 3 x 2 = 18 combinations :

A1, B1, C1
A1, B1, C2
A1, B2, C1
A1, B2, C2
A1, B3, C1
A1, B3, C2
A2, B1, C1
A2, B1, C2 ...

The problem is to create a function with a variable number of source arrays...

Upvotes: 60

Answers (10)

Arnaud Le Blanc

Reputation: 99909

Simple solution with generators and array unpacking:

function combinations(array $arrays): iterable {
    if ($arrays === []) {
        yield [];
        return;
    }

    $head = array_shift($arrays);

    foreach ($head as $elem) {
        foreach (self::combinations($arrays) as $combination) {
            yield [$elem, ...$combination];
        }
    }
}

Try it here: https://3v4l.org/Y8clG

Result:

Array
(
    [0] => Array
        (
            [0] => A1
            [1] => B1
            [2] => C1
        )

    [1] => Array
        (
            [0] => A1
            [1] => B1
            [2] => C2
        )

    [2] => Array
        (
            [0] => A1
            [1] => B2
            [2] => C1
        )

    [3] => Array
        (
            [0] => A1
            [1] => B2
            [2] => C2
        )

    [4] => Array
        (
            [0] => A1
            [1] => B3
            [2] => C1
        )

    [5] => Array
        (
            [0] => A1
            [1] => B3
            [2] => C2
        )

    [6] => Array
        (
            [0] => A2
            [1] => B1
            [2] => C1
        )

    [7] => Array
        (
            [0] => A2
            [1] => B1
            [2] => C2
        )

    [8] => Array
        (
            [0] => A2
            [1] => B2
            [2] => C1
        )

    [9] => Array
        (
            [0] => A2
            [1] => B2
            [2] => C2
        )

    [10] => Array
        (
            [0] => A2
            [1] => B3
            [2] => C1
        )

    [11] => Array
        (
            [0] => A2
            [1] => B3
            [2] => C2
        )

    [12] => Array
        (
            [0] => A3
            [1] => B1
            [2] => C1
        )

    [13] => Array
        (
            [0] => A3
            [1] => B1
            [2] => C2
        )

    [14] => Array
        (
            [0] => A3
            [1] => B2
            [2] => C1
        )

    [15] => Array
        (
            [0] => A3
            [1] => B2
            [2] => C2
        )

    [16] => Array
        (
            [0] => A3
            [1] => B3
            [2] => C1
        )

    [17] => Array
        (
            [0] => A3
            [1] => B3
            [2] => C2
        )

)

Upvotes: 3

aowie1

Reputation: 846

I improved upon the solution given by @mr1031011 to allow the optional preservation of keys

/**
 * Generate an array of permutations from a given array[array[options]]
 * e.g.
 * ['foo' => [null, 'a'], 'bar' => ['b']]
 *
 * will generate:
 * [null, 'b']
 * ['a', 'b']
 *
 * or with preserveKeys = true:
 * ['foo' => null,'bar' => 'b']
 * ['foo' => 'a','bar' => 'b']
 *
 * @param array $array
 * @param bool  $preserveKeys
 *
 * @return Generator
 */
function generatePermutations(array $array, bool $preserveKeys = false): Generator
{
    if ($preserveKeys) {
        end($array);
        $key = key($array);
    }

    foreach (array_pop($array) as $value) {
        $item = isset($key) ? [$key => $value] : [$value];

        if (!count($array)) {
            yield $item;
            continue;
        }

        foreach (generatePermutations($array, $preserveKeys) as $combination) {
            yield array_merge($item, $combination);
        }
    }
}

Upvotes: 0

Doger

Reputation: 171

Here is a code that generates unique combinations from a set of numbers.

If you have a list of numbers, like 1,3,4,7,12 you can generate sets of X numbers, all unique, no repetitive.

The first function works in PHP 7.4 or higher, and the second one uses keys to store the values. Both work very well based on the benchmark.

function get_combos74($map, $size, &$generated = [], $loop = 1, $i = 0, $prefix = [])
{
    if ($loop == 1) {
        sort($map);
    }

    for (; $i < count($map); $i++) {
        if ($loop < $size) {
            get_combos74($map, $size, $generated, $loop + 1, $i + 1, [...$prefix, $map[$i]]);
        } else {
            $generated[] = [...$prefix, $map[$i]];
        }
    }

    return $generated;
}

function get_combosSTR($map, $size, &$generated = [], $loop = 1, $i = 0, $prefix = '')
{
    if ($loop == 1) {
        sort($map);
    }

    for (; $i < count($map); $i++) {
        if ($loop < $size) {
            get_combosSTR($map, $size, $generated, $loop + 1, $i + 1, "$prefix{$map[$i]}:");
        } else {
            $generated["$prefix{$map[$i]}"] = 0;
        }
    }

    return $generated;
}

Upvotes: 2

Ashwin Balani

Reputation: 771

I got this from O'Relly (https://www.oreilly.com/library/view/php-cookbook/1565926811/ch04s25.html),

function pc_array_power_set($array) {
// initialize by adding the empty set
$results = array(array( ));

foreach ($array as $element)
    foreach ($results as $combination)
        array_push($results, array_merge(array($element), $combination));



   return $results;
}

Then call it using,

$set = array('A', 'B', 'C');
$power_set = pc_array_power_set($set);

That should do the trick!

Upvotes: -1

Alexander Ivashchenko

Reputation: 868

I like this solution: https://stackoverflow.com/a/33259643/3163536 but to answer the actual question (which assumes that the number of elements of each combination should be equal to the number of incoming arrays) the function should be modified:

function getCombinations(...$arrays)
    {
        $result = [[]];
        foreach ($arrays as $property => $property_values) {
            $tmp = [];
            foreach ($result as $result_item) {
                foreach ($property_values as $property_value) {
                    $tmp[] = array_merge($result_item, [$property => $property_value]);
                }
            }
            $result = $tmp;
        }
        return $result;
    }

The usage:

$arrayA = array('A1','A2','A3');
$arrayB = array('B1','B2','B3');
$arrayC = array('C1','C2');

print_r(getCombinations($arrayA, $arrayB, $arrayC));

The result:

Array
(
    [0] => Array
        (
            [0] => A1
            [1] => B1
            [2] => C1
        )

    [1] => Array
        (
            [0] => A1
            [1] => B1
            [2] => C2
        )

    [2] => Array
        (
            [0] => A1
            [1] => B2
            [2] => C1
        )

    [3] => Array
        (
            [0] => A1
            [1] => B2
            [2] => C2
        )

    [4] => Array
        (
            [0] => A1
            [1] => B3
            [2] => C1
        )

    [5] => Array
        (
            [0] => A1
            [1] => B3
            [2] => C2
        )

    [6] => Array
        (
            [0] => A2
            [1] => B1
            [2] => C1
        )

    [7] => Array
        (
            [0] => A2
            [1] => B1
            [2] => C2
        )

    [8] => Array
        (
            [0] => A2
            [1] => B2
            [2] => C1
        )

    [9] => Array
        (
            [0] => A2
            [1] => B2
            [2] => C2
        )

    [10] => Array
        (
            [0] => A2
            [1] => B3
            [2] => C1
        )

    [11] => Array
        (
            [0] => A2
            [1] => B3
            [2] => C2
        )

    [12] => Array
        (
            [0] => A3
            [1] => B1
            [2] => C1
        )

    [13] => Array
        (
            [0] => A3
            [1] => B1
            [2] => C2
        )

    [14] => Array
        (
            [0] => A3
            [1] => B2
            [2] => C1
        )

    [15] => Array
        (
            [0] => A3
            [1] => B2
            [2] => C2
        )

    [16] => Array
        (
            [0] => A3
            [1] => B3
            [2] => C1
        )

    [17] => Array
        (
            [0] => A3
            [1] => B3
            [2] => C2
        )

)

Upvotes: 11

Eugene Fedorenko

Reputation: 51

One more idea:

$ar = [
    'a' => [1,2,3],
    'b' => [4,5,6],
    'c' => [7,8,9]
];

$counts = array_map("count", $ar);
$total = array_product($counts);
$res = [];

$combinations = [];
$curCombs = $total;

foreach ($ar as $field => $vals) {
    $curCombs = $curCombs / $counts[$field];
    $combinations[$field] = $curCombs;
}

for ($i = 0; $i < $total; $i++) {
    foreach ($ar as $field => $vals) {
        $res[$i][$field] = $vals[($i / $combinations[$field]) % $counts[$field]];
    }
}

var_dump($res);

Upvotes: 5

Guilhermo Luna

Reputation: 273

This code besides simplicity, get all combinations of multiple arrays and preserves keys.

function get_combinations($arrays) {
    $result = array(array());
    foreach ($arrays as $property => $property_values) {
        $tmp = array();
        foreach ($result as $result_item) {
            foreach ($property_values as $property_key => $property_value) {
                $tmp[] = $result_item + array($property_key => $property_value);
            }
        }
        $result = $tmp;
    }
    return $result;
}

Exemple:

Array
(
    Array
    (
        '1' => 'White',
        '2' => 'Green',
        '3' => 'Blue'
    ),
    Array
    (
        '4' =>' Small',
        '5' => 'Big'
    )
)

Will return:

Array
(
    [0] => Array
    (
        [1] => White
        [4] =>  Small
    )
    [1] => Array
    (
        [1] => White
        [5] => Big
    )
    [2] => Array
    (
        [2] => Green
        [4] =>  Small
    )
    [3] => Array
    (
        [2] => Green
        [5] => Big
    )
    [4] => Array
    (
        [3] => Blue
        [4] =>  Small
    )
    [5] => Array
    (
        [3] => Blue
        [5] => Big
    )
)

Upvotes: 22

mr1031011

Reputation: 3812

I know this question is old, but I got the same issue today and decided to give the new Generator a try:

function generateCombinations(array $array) {
    foreach (array_pop($array) as $value) {
        if (count($array)) {
            foreach (generateCombinations($array) as $combination) {
                yield array_merge([$value], $combination);
            };
        } else {
            yield [$value];
        }
    }
}

foreach (generateCombinations(['a' => ['A'], 'b' => ['B'], 'c' => ['C', 'D'], 'd' => ['E', 'F', 'G']]) as $c) {
        var_dump($c);
    }

Result:

array(4) {
[0]=>
string(1) "E"
[1]=>
string(1) "C"
[2]=>
string(1) "B"
[3]=>
string(1) "A"
}
array(4) {
[0]=>
string(1) "E"
[1]=>
string(1) "D"
[2]=>
string(1) "B"
[3]=>
string(1) "A"
}
array(4) {
[0]=>
string(1) "F"
[1]=>
string(1) "C"
[2]=>
string(1) "B"
[3]=>
string(1) "A"
}
array(4) {
[0]=>
string(1) "F"
[1]=>
string(1) "D"
[2]=>
string(1) "B"
[3]=>
string(1) "A"
}
array(4) {
[0]=>
string(1) "G"
[1]=>
string(1) "C"
[2]=>
string(1) "B"
[3]=>
string(1) "A"
}
array(4) {
[0]=>
string(1) "G"
[1]=>
string(1) "D"
[2]=>
string(1) "B"
[3]=>
string(1) "A"
}

Upvotes: 7

barfoon

Reputation: 28157

This is a cartesian product, and I just asked the same question not too long ago. Here is the algorithm that is posted on the PHP website.

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);
    for ($i = 0; $i < $size; $i ++)
    {
        $result[$i] = array();
        for ($j = 0; $j < $sizeIn; $j ++)
            array_push($result[$i], current($arrays[$j]));
        for ($j = ($sizeIn -1); $j >= 0; $j --)
        {
            if (next($arrays[$j]))
                break;
            elseif (isset ($arrays[$j]))
                reset($arrays[$j]);
        }
    }
    return $result;
}

Upvotes: 19

Krzysztof

Reputation: 16130

Here is recursive solution:

function combinations($arrays, $i = 0) {
    if (!isset($arrays[$i])) {
        return array();
    }
    if ($i == count($arrays) - 1) {
        return $arrays[$i];
    }

    // get combinations from subsequent arrays
    $tmp = combinations($arrays, $i + 1);

    $result = array();

    // concat each array from tmp with each element from $arrays[$i]
    foreach ($arrays[$i] as $v) {
        foreach ($tmp as $t) {
            $result[] = is_array($t) ? 
                array_merge(array($v), $t) :
                array($v, $t);
        }
    }

    return $result;
}

print_r(
    combinations(
        array(
            array('A1','A2','A3'), 
            array('B1','B2','B3'), 
            array('C1','C2')
        )
    )
);

Upvotes: 95

How to generate in PHP all combinations of items in multiple arrays

Answers (10)

Related Questions