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

php arrays recursion permutation

1030 просмотра

2 ответа

121 Репутация автора

У меня есть вопрос, который у меня над головой, надеюсь, кто-то может помочь. Я думаю, что это может быть решено с помощью рекурсии и / или перестановок, но я не достаточно хорош для (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.

Я ищу способ сделать все возможные комбинации. Вот несколько ДЕЙСТВИТЕЛЬНЫХ комбинаций:

Пример 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");

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

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

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

Автор: Tjeerd Kramer Источник Размещён: 04.02.2014 03:47

Ответы (2)

0 плюса

1291 Репутация автора

Решение

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

<?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], у вас будет плохое время.

Автор: luxcem Размещён: 04.02.2014 04:08

0 плюса

5605 Репутация автора

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

Вот 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
...

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

Автор: Redsandro Размещён: 04.02.2014 05:54
Вопросы из категории :
32x32