PHP: Get all combinations of multiple arrays (preserves keys)

get_combinations.php

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

?>

output.txt

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)

Nicely done.

Perfect! Thank you!

Helped me save hours. Thanks :)

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

Finally work, thanks to both @cecilemuller and @AlexeyKosov

Thanks, you saved my time :)

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?

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;

Work's great, thank's!

Thanks Buddy.

Huge help! Thanks!

It's really helpful thanks

thanks very helpful!!

Nice gist, thanks!

Saved me! Thanks!

very short code and helpful!Thanks

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;

}

Thanks! Very helpful!

Saved big hours

Many thanks!

Many many thanks!
You saved me so much time!

thanx. it's very helpful

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!

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