Как получить все возможные перестановки?

Question

[vista1x]

Допустим, есть массив

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

Элементов в массиве может быть любое кол-во.
Из этого массива нужно получить все варианты его перестановок (как ключей, так и значений).
Приведу пример того, что должно получится в итоге:

$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'],],
	// .. и т д
];

Подскажите алгоритм или принцип, никак не могу понять, как вообще написать эту рекурсию)
В идеале это все должно быть максимально оптимально. Если можно сделать так, что бы функция мне каждый раз возвращала бы следующие N элементов последовательности - было бы оптимальнее всего.

Answer 1

[Дмитрий]

Переводите изначальный массив в плоский, содержащий все одиночные значения с добавленным флагом check

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

Теперь все что вам нужно - в цикле получить все варианты с check, алгоритмически проще всего это сделать, представив двоичное число с количеством разрядов равное количеству элементов:
в вашем примере таковых 9, то есть:
000000001
000000010
000000011
000000100
..
111111111

Соответственно алгоритм на каждом шаге такой - ищем в $paramsFlat первый элемент с check === 0, меняем его на единицу, а свойство check всех элементов до него обнуляем

После каждого шага включаете в очередной элемент итогового массива $result только элементы $paramsFlat с check === 1

Функция получения следующего элемента может выглядеть примерно так (не тестировал и не оптимизировал, но смысл полагаю ясен)

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

Comments

[vista1x]

Спасибо! А как я могу исключить варианты с несколькими значениями одного и того же параметра? То есть, по сути, нужно оставить только перестановки разных параметров с одним значением.
Из вот этого

[['option1','1'],],
  [['option1','2'],],
  [['option1','3'],],
  [['option1','1'], ['option1','2'],],
  [['option1','1'], ['option1','3'],],
  [['option1','2'], ['option1','3'],],
  [['option1','1'], ['option1','2'], ['option1','3']],

Должно остатья только

[['option1','1'],],
  [['option1','2'],],
  [['option1','3'],],

При этом должны остаться перестановки между разными параметрами, где каждый параметр так же будет иметь только одно значение.

[Дмитрий]

vista1x, У вас же в примере
[['option1','1'], ['option2', 1], ['option2', 2],],

или в примере неверно?

[vista1x]

Дмитрий, все верно, и предложенный вами вариант отлично работает, спасибо. Просто понадобилось вдобавок генерировать немного по другому принципу

[Дмитрий]

vista1x,

Приведите к виду

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

В каждой итерации увеличивайте св-во 'index' последнего элемента на 1. Если выйдет за пределы массива, возвращайте назад к -1, и прибавляйте единицу к индексу предыдущего.

function getNext($params) {
    
    //начинаем с последнего параметра
    $pos = count($params) - 1;
    
    // Добавляем к значению index единицу, если она равна кол-ву в массиве
    // то присваиваем index -1, и увеличиваем на единицу предыдущий параметр и т.д.
    while(++$params[$pos]['index'] === count($params[$pos]['values'])) {
        $params[$pos]['index'] = -1;
        if(0 === $pos--) break;
    }
    
    if($pos < 0) return false;
    
    // Составляем результат, получая от каждого параметра элемент массива с индексом index
    // Если index === -1, то игнорируем
    $retVal = [];
     foreach($params as $elem) {
        if($elem['index'] >= 0) retVal[] = [$elem['param'], $elem['values'][$elem['index']]];
     }
    
    return $retVal;
}

[vista1x]

Дмитрий, Отлично, большое спасибо!)