Skip to content

Instantly share code, notes, and snippets.

@cecilemuller
Created February 1, 2013 03:13
Show Gist options
  • Save cecilemuller/4688876 to your computer and use it in GitHub Desktop.
Save cecilemuller/4688876 to your computer and use it in GitHub Desktop.
PHP: Get all combinations of multiple arrays (preserves keys)
<?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);
?>
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)
@vinodselvin
Copy link

Nicely done.

@simo-vt
Copy link

simo-vt commented May 15, 2018

Perfect! Thank you!

@sohaibshaheen
Copy link

Helped me save hours. Thanks :)

@AlexeyKosov
Copy link

Heads up: if keys are integer, array_merge should be replaced with array_replace

Copy link

ghost commented Jun 28, 2018

Finally work, thanks to both @cecilemuller and @AlexeyKosov

@IAkumaI
Copy link

IAkumaI commented Sep 7, 2018

Thanks, you saved my time :)

@reymonzakhary
Copy link

This great, but I have big array so if I run your script stops on the have of the combination because of the memory eny idea how to fixe this?

@daiwai
Copy link

daiwai commented Nov 14, 2018

Thanks for sharing. The array_merge is not necessary, though. Setting the new $property_value on $result_item[$property] directly, instead of using array_merge speeds up the function by a factor of about 2, depending on the input.

E.g. replace line 9 with:

$result_item[$property] = $property_value;
$tmp[] = $result_item;

@stephanokrm
Copy link

Work's great, thank's!

@vipinks
Copy link

vipinks commented Apr 27, 2019

Thanks Buddy.

@ajenkins198621
Copy link

Huge help! Thanks!

@mshahzaibwiztech
Copy link

It's really helpful thanks

@raufp6
Copy link

raufp6 commented Aug 26, 2019

thanks very helpful!!

@kwazaro
Copy link

kwazaro commented Aug 26, 2019

Nice gist, thanks!

@danielcmm
Copy link

Saved me! Thanks!

@tsecheng
Copy link

tsecheng commented Sep 3, 2019

very short code and helpful!Thanks

@programadorsergio
Copy link

function get_combinations($arrays) {

$arrays = array_filter($arrays); //for empty index case

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

}

@isteshkov
Copy link

Thanks! Very helpful!

@rajitha-bandara
Copy link

Saved big hours

@pankaj-torinit
Copy link

Many thanks!

@kadiiskiFFW
Copy link

Many many thanks!
You saved me so much time!

@suvo98
Copy link

suvo98 commented Nov 7, 2020

thanx. it's very helpful

@mariusadam
Copy link

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!

@spiritgulshan
Copy link

Thanks...saved my day

@dernoun
Copy link

dernoun commented Mar 16, 2021

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

@vahidalvandi
Copy link

thank you

@mohammadsalem
Copy link

Thanks!

@harish-pixpa
Copy link

Thanks, You save my time

@Ultimater
Copy link

Ultimater commented Jan 5, 2023

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

@fofopp
Copy link

fofopp commented Nov 8, 2023

Thanks! :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment