Created
February 1, 2013 03:13
-
-
Save cecilemuller/4688876 to your computer and use it in GitHub Desktop.
PHP: Get all combinations of multiple arrays (preserves keys)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
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_value) { | |
$tmp[] = array_merge($result_item, array($property => $property_value)); | |
} | |
} | |
$result = $tmp; | |
} | |
return $result; | |
} | |
$combinations = get_combinations( | |
array( | |
'item1' => array('A', 'B'), | |
'item2' => array('C', 'D'), | |
'item3' => array('E', 'F'), | |
) | |
); | |
var_dump($combinations); | |
?> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
array (size=8) | |
0 => | |
array (size=3) | |
'item1' => string 'A' (length=1) | |
'item2' => string 'C' (length=1) | |
'item3' => string 'E' (length=1) | |
1 => | |
array (size=3) | |
'item1' => string 'A' (length=1) | |
'item2' => string 'C' (length=1) | |
'item3' => string 'F' (length=1) | |
2 => | |
array (size=3) | |
'item1' => string 'A' (length=1) | |
'item2' => string 'D' (length=1) | |
'item3' => string 'E' (length=1) | |
3 => | |
array (size=3) | |
'item1' => string 'A' (length=1) | |
'item2' => string 'D' (length=1) | |
'item3' => string 'F' (length=1) | |
4 => | |
array (size=3) | |
'item1' => string 'B' (length=1) | |
'item2' => string 'C' (length=1) | |
'item3' => string 'E' (length=1) | |
5 => | |
array (size=3) | |
'item1' => string 'B' (length=1) | |
'item2' => string 'C' (length=1) | |
'item3' => string 'F' (length=1) | |
6 => | |
array (size=3) | |
'item1' => string 'B' (length=1) | |
'item2' => string 'D' (length=1) | |
'item3' => string 'E' (length=1) | |
7 => | |
array (size=3) | |
'item1' => string 'B' (length=1) | |
'item2' => string 'D' (length=1) | |
'item3' => string 'F' (length=1) |
Thanks...saved my day
The solution works but it's extremely expansive in term time complexity, it will take O(n^) where ^ = number of arrays + 1.
I suggest this solution that is written in Java and accept any Type, put all your arrays inside one array and execute your task
public static <T> void getNumberOfOptions(List<List<T>> arr) {
// Number of arrays
int n = arr.size();
// To keep track of next element in
// each of the n arrays
int []indices = new int[n];
// Initialize with first element's index
for(int i = 0; i < n; i++)
indices[i] = 0;
while (true)
{
// Print current combination
for(int i = 0; i < n; i++) {
System.out.print(
arr.get(i).get(indices[i]) + " ");
}
System.out.println();
// Find the rightmost array that has more
// elements left after the current element
// in that array
int next = n - 1;
while (next >= 0 &&
(indices[next] + 1 >=
arr.get(next).size()))
next--;
// No such array is found so no more
// combinations left
if (next < 0)
break;
// If found move to next element in that
// array
indices[next]++;
// For all arrays to the right of this
// array current index again points to
// first element
for(int i = next + 1; i < n; i++)
indices[i] = 0;
}
}
thank you
Thanks!
Thanks, You save my time
Here's a PHP version of dernoun's Java solution.
function getNumberOfOptions(array $arr): void {
$n = count($arr);
$indices = array_fill(0, $n, 0);
while(true) {
// grab current combination for the indices.
for($i = 0; $i < $n; $i++) {
echo $arr[$i][$indices[$i]] . ' ';
}
echo "\n";
// Find the rightmost array that has more
// elements left after the current element
// in that array
$next = $n - 1;
while($next >= 0 &&
($indices[$next] + 1 >=
count($arr[$next]))
) {
$next--;
}
// No such array is found so no more
// combinations left
if ($next < 0)
break;
// If found move to next element in that
// array
$indices[$next]++;
// For all arrays to the right of this
// array current index again points to
// first element
for($i = $next + 1; $i < $n; $i++) {
$indices[$i] = 0;
}
}
}
Or if we change the function to instead return the array of combinations rather than print them, it would look like this:
function get_combinations(array $arrays): array {
$n = count($arrays);
$indices = array_fill(0, $n, 0);
$combinations = [];
while(true) {
// grab current combination for the indices.
$combination = [];
for($i = 0; $i < $n; $i++) {
$combination[] = $arrays[$i][$indices[$i]];
}
$combinations[] = $combination;
// Find the rightmost array that has more
// elements left after the current element
// in that array
$next = $n - 1;
while($next >= 0 &&
($indices[$next] + 1 >=
count($arrays[$next]))
) {
$next--;
}
// No such array is found so no more
// combinations left
if ($next < 0)
break;
// If found move to next element in that
// array
$indices[$next]++;
// For all arrays to the right of this
// array current index again points to
// first element
for($i = $next + 1; $i < $n; $i++) {
$indices[$i] = 0;
}
}
return $combinations;
}
Thanks! :)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thanks, it helped me as well. At first I didn't understand why it does exactly what I want, even covering the case of one the arrays being empty, but doing a step by step execution clarified things. Nice job!