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
– goat

2011-12-19 20:30:06 +00:00
Commented Dec 19, 2011 at 20:30 — goat
– goat, Commented Dec 19, 2011 at 20:30

Krzysztof · Accepted Answer · 2011-12-19 20:56:32Z

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, 2011 at 20:56

answered Dec 19, 2011 at 20:34

Krzysztof

16.2k2 gold badges52 silver badges79 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Alex Angelico Over a year ago

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?

Daniel Brose Over a year ago

@AlexAngelico - and for anyone else with same question, see array_unique, php.net/manual/en/function.array-unique.php

Tahiaji Over a year ago

It's an old answer. But the solution did not work as expected if pass a single array like [['A1','A2','A3']]

toof06 Over a year ago

it doesn't work for single array if you need a good solution work for me very well stackoverflow.com/a/76196962/10500869

gadlol Feb 23 at 1:32

Note: this function produces "Fatal error: Allowed memory size of..." on array_merge function when using big array of arrays.

amlette · Accepted Answer · 2017-06-07 21:44:30Z

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

Community · Accepted Answer · 2017-05-23 12:02:32Z

20

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, 2017 at 12:02

CommunityBot

11 silver badge

answered Dec 19, 2011 at 20:58

barfoon

28.5k29 gold badges97 silver badges140 bronze badges

2 Comments

JohnK Over a year ago

The link to the PHP website doesn't apparently lead anything about this function. Could you give an example of invoking it?

Richard - Rogue Wave Limited Over a year ago

This function takes over 2.5 times as long as Lolo's function to process the same array.

Alexander Ivashchenko · Accepted Answer · 2020-01-08 15:30:57Z

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
        )

)

mr1031011 · Accepted Answer · 2016-02-19 16:50:43Z

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, 2016 at 16:50

mr1031011

3,8428 gold badges46 silver badges61 bronze badges

5 Comments

Pol Dellaiera Over a year ago

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.

clarkk Over a year ago

this is the most simple solution

Glasset Over a year ago

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 Over a year ago

workaround for my question: create array like that ['a' => [['key' => 'a', 'value' => 'A'], ['key' => 'a', 'value' => 'n']]]

qwertynik Over a year ago

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.

Eugene Fedorenko · Accepted Answer · 2018-04-12 10:22:12Z

5

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

answered Apr 12, 2018 at 10:22

Eugene Fedorenko

511 silver badge1 bronze badge

Comments

Arnaud Le Blanc · Accepted Answer · 2022-01-21 12:00:01Z

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
        )

)

F. Müller · Accepted Answer · 2020-11-19 19:39:59Z

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

aowie1 · Accepted Answer · 2021-04-09 19:32:23Z

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

Ashwin Balani · Accepted Answer · 2020-06-26 06:51:22Z

-2

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!

answered Jun 26, 2020 at 6:51

Ashwin Balani

7799 silver badges19 bronze badges

Collectives™ on Stack Overflow

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

10 Answers 10

5 Comments

Comments

2 Comments

Comments

5 Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

10 Answers 10

5 Comments

Comments

2 Comments

Comments

5 Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related