How to get all possible permutations?

Question

PHP

Let's say we have an array

$params = [
  'option1' => [1, 2, 3],
  'option2' => [1, 2, 3, 4],
  'option3' => [1, 2],
];

There can be any number of elements in an array.
From this array, you need to get all the options for its permutations (both keys and values).
Here is an example of what should be the result:

$result = [
  [['option1','1'],],
  [['option1','2'],],
  [['option1','3'],],
  [['option1','1'], ['option1','2'],],
  [['option1','1'], ['option1','3'],],
  [['option1','2'], ['option1','3'],],
  [['option1','1'], ['option1','2'], ['option1','3']],

  [['option2', 1],],
  [['option2', 2],],
  [['option2', 3],],
  [['option2', 4],],
  [['option2', 1], ['option2', 2],],
  [['option2', 1], ['option2', 3],],
  [['option2', 1], ['option2', 4],],
  [['option2', 2], ['option2', 2],],
  [['option2', 2], ['option2', 3],],
  [['option2', 2], ['option2', 4],],
  [['option2', 3], ['option2', 3],],
  [['option2', 3], ['option2', 4],],
  [['option2', 4], ['option2', 4],],
  [['option2', 1], ['option2', 2], ['option2', 3],],
  [['option2', 1], ['option2', 2], ['option2', 4],],
  [['option2', 1], ['option2', 3], ['option2', 4],],
  [['option2', 1], ['option2', 2], ['option2', 3], ['option2', 4]],
  
  [['option3','1'],],
  [['option3','2'],],
  [['option3','1'], ['option3','2'],],

  // а теперь самое интересное
  [['option1','1'], ['option2', 1],],
  [['option1','1'], ['option2', 2],],
  [['option1','1'], ['option2', 3],],
  [['option1','1'], ['option2', 4],],
  [['option1','1'], ['option2', 1], ['option2', 2],],
  // ...
  [['option1','1'], ['option1','2'], ['option2', 1],],
  // ...
  [['option1','1'], ['option2', 1], ['option3','1'],],
  // .. и т д
];

Tell me the algorithm or principle, I just can’t figure out how to write this recursion at all)
Ideally, this should all be as optimal as possible. If it is possible to make it so that the function would return the next N elements of the sequence to me each time, it would be the most optimal.

Answer 1

Convert the original array to a flat array containing all single values ​​with the check flag added

$paramsFlat = [
  ['value' => ['option1' => 1], 'check' => 0],
  ['value' => ['option1' => 2], 'check' => 0],
  ...
  ['value' => ['option3' => 2], 'check' => 0],
];

Now all you need is to get all the options with check in the loop, the algorithmically easiest way to do this is by presenting a binary number with the number of digits equal to the number of elements:
in your example there are 9, that is :
000000001
000000010
000000011
000000100
.. step like this - look in $paramsFlat for the first element with check === 0, change it to one, and reset the check property of all elements before it. After each step, include in the next element of the final array $result only elements of $paramsFlat with check === 1 The function for getting the next element may look something like this (did not test or optimize, but I think the meaning is clear)

function getNext($paramsFlat) {
    foreach($paramsFlat as &$elem) {
        // Инвертируем значения до первого найденного нуля
        if($elem['checked'] = !$elem['checked']) break;    
    }
    
    // Получаем массив, содержащий отмеченные элементы
    $retVal = array_filter($paramsFlat, function($v) {return $v['checked'];});
    if(!count($retVal)) return false;
    
    // Возвращаем массив из значений отмеченных элементов
    return array_map(function($v) {return $v['value'];}, $paramsFlat);
}