How to generate in PHP all combinations of items in multiple arrays
PhpArraysCombinationsIterationPhp Problem Overview
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...
Php Solutions
Solution 1 - Php
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')
)
)
);
Solution 2 - Php
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;
}
Solution 3 - Php
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
)
)
Solution 4 - Php
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
)
)
Solution 5 - Php
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"
}
Solution 6 - Php
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);
Solution 7 - Php
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;
}
Solution 8 - Php
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);
}
}
}
Solution 9 - Php
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
)
)
Solution 10 - Php
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!