Все возможные комбинации в массиве – рекурсия?

У меня есть вопрос, который проходит над моей головой, надеюсь, что кто-то может помочь. Я думаю, что его, возможно, придется решать путем рекурсии и / или перестановок, но я недостаточно хорош для программиста (PHP).

$map[] = array("0", "1", "2", "3"); $map[] = array("4", "5", "6", "7"); $map[] = array("8", "9", "10", "11"); $map[] = array("12", "13", "14", "15"); $map[] = array("16", "17", "18", "19"); $map[] = array("20", "21", "22", "23"); 

Массив $ map ограничен максимальной длиной «6».

Я ищу способ сделать все возможные комбинации. Вот несколько комбинаций VALID:

Пример 1:

 $map[] = array("0", "1", "2", "3", "4", "5", "6", "7"); $map[] = array("8", "9", "10", "11"); $map[] = array("12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", ); $map[] = array("23"); 

Пример 2:

 $map[] = array("0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23"); 

Пример 3:

 $map[] = array("0", "1"); $map[] = array("2", "3", "4", "5", "6", "7", "8"); $map[] = array("9", "10", "11"); $map[] = array("12"); $map[] = array("13", "14", "15", "16", "17", "18", "19", "20"); $map[] = array("21", "22", "23"); 

Значения в каждом из массивов карт должны быть в порядке возрастания, например, этот пример является INVALID:

 $map[] = array("0", "1", "4"); $map[] = array("3", "5"); etc... 

Надеюсь, это можно сделать.

Solutions Collecting From Web of "Все возможные комбинации в массиве – рекурсия?"

Рекурсивное решение.

 <?php function combination($remaining, $current, $combinations) { $e = array_shift($remaining); $combinations[$current][] = $e; if(empty($remaining)) { print_r($combinations); return; } combination($remaining, $current, $combinations); // 6 Limit remove for all solutions if ($current < 6) { combination($remaining, $current + 1, $combinations); } } $remaining = range(0, 23); combination($remaining, 0, array()); 

Если вы хотите сохранить все решения для [0,23], у вас будет плохое время.

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

Вот shellscript (который выполняется с терминала как скрипт node.js ), который вычисляет диапазоны, которые вы хотите:

 #!/usr/bin/env nodejs // Config var blocksTotal = 3; // 6 var numbersTotal = 6; // 24 var perms = []; // Permutations // Start the loop (function divideHours(numbersToGo, blocksToGo, arr) { // What block is this? [1 .. 3] var block = blocksTotal - --blocksToGo; // Divide numbers if (block < blocksTotal) for (var hour = 0; hour <= numbersToGo; hour++) { if (block == 1) var arr = []; arr[block-1] = hour; divideHours(numbersToGo-hour, blocksToGo, arr); } // Last block? Assign rest of numbers else { perms.push(arr.concat([numbersToGo])); console.log(arr.concat([numbersToGo]).toString()); } })(numbersTotal, blocksTotal); 

При тестировании с меньшим набором диапазонов и чисел вы получаете следующие перестановки:

0,0,6
0,1,5
0,2,4
0,3,3
0,4,2
0,5,1
0,6,0
1,0,5
1,1,4
1,2,3
1,3,2
1,4,1
1,5,0
2,0,4
2,1,3
2,2,2
2,3,1
2,4,0
3,0,3
3,1,2
3,2,1
3,3,0
4,0,2
4,1,1
4,2,0
5,0,1
5,1,0
6,0,0

Кажется, что? Теперь попробуйте большие числа, результирующий массив хранится в perms .

Если вы явно хотите, чтобы каждое число упоминалось в массиве, вы можете использовать некоторые счетчики и математику для получения такого массива вместо этого. Например:
3,1,2 -> [1,2,3],[4],[5,6]
2,0,4 -> [1,2],[],[3,4,5,6]

Вот фрагмент, который использует 6 блоков и 24 номера:


7,2,2,10,0,3
7,2,2,10,1,2
7,2,2,10,2,1
7,2,2,10,3,0
7,2,2,11,0,2
7,2,2,11,1,1
7,2,2,11,2,0
7,2,2,12,0,1
7,2,2,12,1,0
7,2,2,13,0,0
7,2,3,0,0,12
7,2,3,0,1,11
7,2,3,0,2,10

.. но этот список бесконечен.