How to generate in PHP all possible selections of items in multiple arrays to cache a filter system

I have created a filter system, You can filter results on multiple taxonomies.

For example: Show all news articles and videos that are in the categories gaming and productivity and with the tag hardware, you could make a selection like this

Content Type
[x] news article
[x] video
[ ] opinion

Category
[x] gaming
[x] productivity
[ ] music

Tags
[x] hardware
[ ] software

This can be represented in an array like this:

[ [ 'news article', 'video' ], [ 'gaming', 'productivity' ], [ 'hardware' ] ];

Now basically what I want is to get an array containing all possible combinations. So it would start like this:

[
  [ [], [], [], ], // no selections
  [ ['news article'], [], [], ], // only news article selected
  [ ['video'], [], [], ],
  [ ['opinion'], [], [], ],
  [ ['news article, video'], [], [], ],
  [ ['news article, opinion'], [], [], ],
  [ ['video, opinion'], [], [], ],
  [ ['news article'], ['gaming'], [], ],
  ...
  [ ['news article', 'video', 'opinion'], ['gaming', 'productivity', 'music'], ['hardware','software'], ],
];

This seems like a common enough problem, but the only combination algorithms I found so far are ones that make combinations with only one element from each array. I realize that the set of combinations that I want to create would become outrageously large incredibly fast, but is there a known approach or PHP function that I could use to generate an array like this?

Answer

First, use the following function to generate all possible choices:

function array_combine_values($array)
{
    $len = count($array);
    $result = [];
    for($i = 0; $i < pow(2, $len); $i++) {
        $row = [];
        $indexes = str_split(str_pad(decbin($i), $len, '0', STR_PAD_LEFT));
        foreach($indexes as $key => $index) {
            if ($index) $row[] = $array[$key];
        }
        $result[] = $row;
    }
    return $result;
}

Example:

print_r(array_combine_values(['a', 'b']));

Output:

Array
(
    [0] => Array
        (
        )
    [1] => Array
        (
            [0] => b
        )
    [2] => Array
        (
            [0] => a
        )
    [3] => Array
        (
            [0] => a
            [1] => b
        )
)

Second, the function of the Cartesian product of arrays:

function array_cartesian_product($array)
{
    if (empty($array)) return [[]];

    $column = array_shift($array);
    $cartesian = array_cartesian_product($array);

    $result = [];
    foreach ($column as $row) {
        foreach ($cartesian as $item) {
            array_unshift($item, $row);
            $result[] = $item;
        }
    }
    return $result;        
}

Example:

print_r(array_cartesian_product([['a', 'b'], ['c', 'd']]));

Output:

Array
(
    [0] => Array
        (
            [0] => a
            [1] => c
        )
    [1] => Array
        (
            [0] => a
            [1] => d
        )
    [2] => Array
        (
            [0] => b
            [1] => c
        )
    [3] => Array
        (
            [0] => b
            [1] => d
        )
)

Usage in your case:

$selections = array( 
    ['news article', 'video', 'opinion'], 
    ['gaming', 'productivity', 'music'], 
    ['hardware','software']
);

$result = [];

foreach($selections as $items) {
    $result[] = array_combine_values($items);
}

$result = array_cartesian_product($result);

print_r($result);