Robbert Robbert - 2 months ago 6
PHP Question

How can I generate all unique combinations of multiple array's with optionals?

I would like to combine all values in multiple array's to create unique combinations. There is one catch: some array's can be optional.

For example: I'm configuring a PC and I've got the choice between:


  • 5 types of chassis (including fans, PSU and main board)

  • 5 types of disks (optional)

  • 5 types of memory (optional)

  • 5 types of video cards (optional)



As you can see the outcome can be any of the combinations:


  1. Chassis type 1, Disk type 3, Memory type 5, video card type 1

  2. Chassis type 1, Disk type 3, Memory type 5, video card type 2

  3. Chassis type 1, Disk type 3, Memory type 5, video card type 3

  4. Chassis type 1, no disk, Memory type 5, video card type 2

  5. Chassis type 1, no disk, Memory type 5, no video card

  6. Chassis type 1, no disk, no memory, no video card

  7. etc.



To determine if a range of products is optional, the
'optional' => [0|1]
part has been included in the array :-)

The following array is an extract of an array used in 'production' that should be combined:

array(
array('optional' => 0, 0, 1),
array('optional' => 0, 3, 4),
array('optional' => 0, 6, 7, 8),
array('optional' => 1, 6, 7, 8, 2),
array('optional' => 1, 6, 7, 8, 5, 9),
array('optional' => 1, 6, 7, 8, 10, 11, 12)
)


The output should be something like:

0, 3, 6
0, 3, 7
0, 3, 8
0, 4, 6
0, 4, 7
0, 4, 8
1, 3, 6
1, 3, 7
1, 3, 8
[...]
0, 3, 6, 2 <-- outcome with an optional product from the 4th array
0, 3, 7, 9 <-- outcome with an optional product from the 5th array
0, 3, 8, 12 <-- outcome with an optional product from the 6th array


As you can see the array's above are combined into one array. Some of the sub array's are mandatory, where optional = 0, or optional where optional = 1.

Before there were optional array's I've used the following function:

<?PHP
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];
}
}
}
?>


This was used via:

foreach ( generateCombinations($ArrCombinateMe) as $combination ){
// Some code here
}


The function worked perfectly so I would like to use something similar and to be precise I do not want to lose the generator function as it is really memory friendly (my previous function would combine everything before returning usable output, which could only return 3.2 million combinations at 4GB of memory. This function already passed the 3.2 million during tests in a thousandfold).

Currently I would love to also include the optional array's so that these are also being generated :-)

Please note: I love speed but for this function this doesn't matter that much as it will run as a background job without any user interaction.

I hope someone can help me out :-)

Answer

It seems that answer is much more simple than understanding the problem. You need no change in procedure - just include 'null' as possible value in optional arrays. It would mean that part wasn't included.

This way there will be arrays with null values returned, but their indexes will represent source. Taking array below for example:

$data = array(
    'Chassis'   => array(0, 1, 2),
    'Mainboard' => array(3, 4, 5),
    'PSU'       => array(6, 7, 8),
    'Disk'      => array(null, 9, 10),
    'GFX'       => array(null, 11, 12),
    'Memory'    => array(null, 13, 14, 15)
);

One of the results would be: [0,3,6,null,11,null]* which means that GFX was included.

You could filter that result if you don't want empty values with

array_filter($combination, 'is_int')

'is_int' param is needed only to handle 0 correctly. If 0 is not valid id then you might skip it (and may use 0 instead of null then)

*) actually last element jumps to first position because of array_merge() args order