Поиск каждой комбинации элементов, включающей одно значение из каждой строки в двумерном массиве в PHP

Question

Я использую большие массивы в своем проекте, но для упрощения, скажем, у нас есть этот массив 3x3:

$a = Array( Array(1,2,3),
            Array(4,5,6),
            Array(7,8,9) );

Я хочу найти каждую комбинацию сумм, которая включает одно значение из каждой строки, т.е. 1 + 4 + 7, 1 + 4 + 8, 1 + 4 + 9, 1 + 5 + 7, 1 + 5 + 8 , 1 + 5 + 9, 1 + 6 + 7, 1 + 6 + 8, 1 + 6 + 9, 2 + 4 + 7, 2 + 4 + 8, 2 + 4 + 9, 2 + 5 + 7,. ..

Надеюсь, картина очевидна. Сначала я попробовал вложенный цикл (столбцы, затем строки), но он не предоставил всех комбинаций. После долгих поисков я уверен, что решение требует рекурсии, но каждый раз, когда я пытаюсь написать рекурсивную функцию для этого, я запутываюсь.

Хотя рабочий код будет очень важен, для меня, пожалуй, важнее будет понимание проблемы и решения.

Answer 1

Учитывая неизвестное количество строк и столбцов в массиве, лучший способ получить желаемый результат - использовать рекурсию (в противном случае вам придется написать произвольное количество вложенных циклов).Эта функция рекурсивно обрабатывает каждую строку в массиве и возвращает один из двух результатов:

1. Если мы находимся в последней строке в массиве, вернуть эту строку;
2. В противном случае вернутьперекрестное произведение (с использованием двух вложенных циклов foreach) между текущей строкой и результатом баланса массива.Мы используем array_shift, чтобы получить текущую строку и удалить ее из массива.

Вот код:

function find_paths($array) {
    if (count($array) == 1) return $array[0];
    $output = array();
    foreach (array_shift($array) as $v1) {
        foreach (find_paths($array) as $v2) {
            $output[] = array_merge(array($v1), is_array($v2) ? $v2 : array($v2));
        }
    }
    return $output;
}

Использование вашегопример данных:

$a = Array( Array(1,2,3),
            Array(4,5,6),
            Array(7,8,9) );
$combinations = find_paths($a);

Функция выполняет эту серию операций:

1. принимает перекрестное произведение строки 1 (1, 2, 3) с выводом функции для балансамассив ((4, 5, 6), (7, 8, 9));
2. Первая рекурсия : взять кросс-произведение строки 2 (4, 5, 6) с выводом функции для баланса массива ((7, 8, 9));
3. Вторая рекурсия : На данный момент в массиве осталась только одна строка (7, 8, 9), поэтому мы ее возвращаем;
4. Первая рекурсия : Вычисляем крестпроизведение (4, 5, 6) с (7, 8, 9) = ((4, 7), (4, 8), (4, 9), (5, 7), (5, 8), (5, 9), (6, 7), (6, 8), (6, 9)) и вернем это;
5. Возьмите перекрестное произведение (1, 2, 3) с ((4, 7), (4, 8), (4, 9), (5, 7), (5, 8), (5, 9), (6, 7), (6, 8), (6, 9)) и вернем это.

Даваявывод:

Array (
    [0] => Array ( [0] => 1 [1] => 4 [2] => 7 )
    [1] => Array ( [0] => 1 [1] => 4 [2] => 8 )
    [2] => Array ( [0] => 1 [1] => 4 [2] => 9 )
    [3] => Array ( [0] => 1 [1] => 5 [2] => 7 )
    [4] => Array ( [0] => 1 [1] => 5 [2] => 8 )
    [5] => Array ( [0] => 1 [1] => 5 [2] => 9 )
    [6] => Array ( [0] => 1 [1] => 6 [2] => 7 )
    [7] => Array ( [0] => 1 [1] => 6 [2] => 8 )
    [8] => Array ( [0] => 1 [1] => 6 [2] => 9 )
    [9] => Array ( [0] => 2 [1] => 4 [2] => 7 )
   [10] => Array ( [0] => 2 [1] => 4 [2] => 8 )
   [11] => Array ( [0] => 2 [1] => 4 [2] => 9 )
   [12] => Array ( [0] => 2 [1] => 5 [2] => 7 )
   [13] => Array ( [0] => 2 [1] => 5 [2] => 8 )
   [14] => Array ( [0] => 2 [1] => 5 [2] => 9 )
   [15] => Array ( [0] => 2 [1] => 6 [2] => 7 )
   [16] => Array ( [0] => 2 [1] => 6 [2] => 8 )
   [17] => Array ( [0] => 2 [1] => 6 [2] => 9 )
   [18] => Array ( [0] => 3 [1] => 4 [2] => 7 )
   [19] => Array ( [0] => 3 [1] => 4 [2] => 8 )
   [20] => Array ( [0] => 3 [1] => 4 [2] => 9 )
   [21] => Array ( [0] => 3 [1] => 5 [2] => 7 )
   [22] => Array ( [0] => 3 [1] => 5 [2] => 8 )
   [23] => Array ( [0] => 3 [1] => 5 [2] => 9 )
   [24] => Array ( [0] => 3 [1] => 6 [2] => 7 )
   [25] => Array ( [0] => 3 [1] => 6 [2] => 8 )
   [26] => Array ( [0] => 3 [1] => 6 [2] => 9 )
)

Если вы хотите получить суммы, вы можете просто использовать array_map в массиве, вызывая array_sum дляGEt сумма каждого элемента:

$sums = array_map(function ($v) { return array_sum($v);}, $combinations);

Вывод:

Array (
    [0] => 12
    [1] => 13
    [2] => 14
    [3] => 13
    [4] => 14
    [5] => 15
    [6] => 14
    [7] => 15
    [8] => 16
    [9] => 13
   [10] => 14
   [11] => 15
   [12] => 14
   [13] => 15
   [14] => 16
   [15] => 15
   [16] => 16
   [17] => 17
   [18] => 14
   [19] => 15
   [20] => 16
   [21] => 15
   [22] => 16
   [23] => 17
   [24] => 16
   [25] => 17
   [26] => 18 
)

Демонстрация на 3v4l.org

Answer 2

Поработав с этим в течение некоторого времени, я нашел другое решение, которое намного быстрее и использует намного меньше памяти, чем ни Ник, ни мои оригинальные ответы.Это становится важным при использовании больших и более многочисленных массивов.Например, вместо 3 на 3 (27 комбинаций), попробуйте 9 на 9 (134 миллиона комбинаций).

Ник по-прежнему заслуживает принятого ответа за предоставление кода, который не только работает, как требуется, но и хорошо объяснен.,Кроме того, этот код заимствует некоторую логику из кода Ника.

Хитрость в производительности заключается в том, что вместо того, чтобы находить все комбинации и затем получать суммы, мы получаем только суммы.Таким образом, мы не создаем потенциально массивный массив массивов, а только один потенциально массивный массив.

Редактирование: Передача $sums по ссылке вместо использования array_merge экономит значительно больше времени и памяти.Код обновлен.

function combo_sums($arrays, $sum = 0, &$sums = []) {
    $array = array_shift($arrays);
    if (count($arrays) > 0)
        foreach ($array as $value)
            combo_sums($arrays, $sum + $value, $sums);
    else
        foreach ($array as $value)
            $sums[] = $sum + $value; # These are the final sums.
    return $sums;
}

Answer 3

После дополнительных поисков я нашел решение здесь: https://gist.github.com/cecilemuller/4688876

Я проверил это на примере моего примера выше, и он дал именно те комбинации, которые мне были нужны. Использование array_map для нахождения сумм, как в ответе Ника, работает как ожидалось.

К моему удивлению, он основан не на рекурсии, а на трех вложенных циклах. Надеюсь, я смогу обернуть голову, как это работает.