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

Question

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

You always want one element from *each* array? – goat Dec 19 '11 at 20:30 — goat, Dec 19 '11 at 20:30

Krzysztof · Accepted Answer · 2011-12-19T20:56:32.673

95

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')
        )
    )
);

edited Dec 19 '11 at 20:56

answered Dec 19 '11 at 20:34

Krzysztof

15,900
2
46
76

how should I change this function if I want the unique combinations for duplicated arrays? For instance, if I have array('A1','A2','A3'), array('A1','A2','A3'), array('C1','C2') and I want as result "A1, A2, C1", "A1, A3, C1", etc, but NO "A1, A1, C1" ? Also (if I'm not asking too much ;) , {"A1", "A2", "C1"} it's the same that {"A2", "A1", "C1"} so I only want 1 combination? – Alex Angelico May 30 '13 at 01:23
@AlexAngelico - and for anyone else with same question, see array_unique, http://php.net/manual/en/function.array-unique.php – Daniel Brose Apr 04 '17 at 03:25
It's an old answer. But the solution did not work as expected if pass a single array like ```[['A1','A2','A3']]``` – Tahiaji Mar 13 '23 at 13:12
it doesn't work for single array if you need a good solution work for me very well https://stackoverflow.com/a/76196962/10500869 – toof06 May 08 '23 at 06:02

score 20 · Answer 2 · edited Jun 07 '17 at 21:44

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
    )
)

this solution worked perfectly for me, had to tweak a bit to combine multiple associative arrays. — mk1024, Nov 07 '18 at 18:01

score 18 · Answer 3 · edited May 23 '17 at 12:02

18

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;
}

edited May 23 '17 at 12:02

Community

1
1

answered Dec 19 '11 at 20:58

barfoon

27,481
26
92
138

The link to the PHP website doesn't apparently lead anything about this function. Could you give an example of invoking it? – JohnK Jul 09 '14 at 00:28
This function takes over 2.5 times as long as Lolo's function to process the same array. – Richard - Rogue Wave Limited Sep 11 '14 at 16:26

score 11 · Answer 4 · answered Jan 08 '20 at 15:30

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
        )

)

score 7 · Answer 5 · answered Feb 19 '16 at 16:50

7

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"
}

answered Feb 19 '16 at 16:50

mr1031011

3,574
5
42
59

When the order doesn't matter, it is a Combination. When the order does matter it is a Permutation. In this case, it's a Permutation and not a Combination. – Pol Dellaiera Dec 20 '16 at 21:01
this is the most simple solution – clarkk Mar 27 '18 at 21:04
is there a way to achieve this ? `array(4) { 'd' => string(1) "E" 'c' => string(1) "C" 'b' => string(1) "B" 'a' => string(1) "A" }` – Glasset Mar 29 '18 at 14:36
workaround for my question: create array like that `['a' => [['key' => 'a', 'value' => 'A'], ['key' => 'a', 'value' => 'n']]]` – Glasset Mar 29 '18 at 14:45
Just in case someone wants the first array's items to appear at the first use `array_shift` instead of `array_pop` at line 2. – qwertynik Feb 23 '22 at 05:48

score 5 · Answer 6 · answered Apr 12 '18 at 10:22

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);

score 2 · Answer 7 · edited Nov 19 '20 at 19:39

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;
}

score 1 · Answer 8 · answered Jan 21 '22 at 12:00

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
        )

)

score 0 · Answer 9 · answered Apr 09 '21 at 19:32

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);
        }
    }
}

score -1 · Answer 10 · answered Jun 26 '20 at 06:51

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!

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

10 Answers10

Linked

Related