Генерация перестановок из массивов
Я попытался портировать функцию, которая генерирует перестановки из этого ответ на PHP, и я вышел со следующим:
function recurse($s, $arrs, $k) {
if ($k === count($arrs)) {
echo $s.' ';
} else {
foreach ($arrs[$k] as $o) {
recurse($s.$o, $arrs, $k + 1);
}
}
}
что дает мне правильный вывод
137 138 147 148 237 238 247 248
Теперь я хочу иметь вывод в виде массива, а не в виде строки, но после редактирования по какой-то причине я получаю неправильные результаты:
function generatePermutations($s, $arrs, $k) {
if ($k === count($arrs)) {
print_r($s);
} else {
foreach ($arrs[$k] as $o) {
$s[] = $o;
generatePermutations($s, $arrs, $k + 1);
}
}
}
Выход:
массив ( [0] => 1 [1] => 3 [2] => 7 ) массив ( [0] => 1 [1] => 3 [2] => 7 [3] => 8 ) массив ( [0] => 1 [1] => 3 [2] => 4 [3] => 7 ) массив ( [0] => 1 [1] => 3 [2] => 4 [3] => 7 [4] => 8 ) массив ( [0] => 1 [1] => 2 [2] => 3 [3] => 7 ) массив ( [0] => 1 [1] => 2 [2] => 3 [3] => 7 [4] => 8 ) массив ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 7 ) массив ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 7 [5] => 8 )
Это вход для обеих функций
$in = array( array(1, 2), array(3, 4), array(7, 8) );
recurse("", $in, 0);
generatePermutations(array(), $in, 0);
Что я сделал не так?
Решение
если вы используете $ s [] = $ o; в вашей рекурсивной функции он будет разрезать ваш массив для каждой цифры.
Вы можете добавить параметр «result», который будет хранить ваш набор результатов в виде массива.
Обратите внимание на & знак. Без него параметр не «доступен для записи», только «доступен для чтения».
$in = array( array(1, 2), array(3, 4), array(7, 8) );
$result = array();
generatePermutations("", $in, 0, $result);
print_r($result);
function generatePermutations($s, $arrs, $k, &$result) {
if ($k === count($arrs)) {
$result[] = $s;
} else {
foreach ($arrs[$k] as $o) {
generatePermutations($s.$o, $arrs, $k + 1, $result);
}
}
}
Выход :
Array
(
[0] => 137
[1] => 138
[2] => 147
[3] => 148
[4] => 237
[5] => 238
[6] => 247
[7] => 248
)
Редактировать: Модификация, чтобы получить ожидаемый результат Robotex:
$in = array( array(1, 2), array(3, 4), array(7, 8) );
$result = array();
$s = array();
generatePermutations($s, $in, 0, $result);
print_r($result);
function generatePermutations(&$s, $arrs, $k, &$result) {
if ($k === count($arrs)) {
array_push($result, $s);
} else {
foreach ($arrs[$k] as $o) {
array_push($s, $o);
generatePermutations($s, $arrs, $k + 1, $result);
array_pop($s);
}
}
}
Выход :
Array
(
[0] => Array
(
[0] => 1
[1] => 3
[2] => 7
)
[1] => Array
(
[0] => 1
[1] => 3
[2] => 8
)
[2] => Array
(
[0] => 1
[1] => 4
[2] => 7
)
[3] => Array
(
[0] => 1
[1] => 4
[2] => 8
)
[4] => Array
(
[0] => 2
[1] => 3
[2] => 7
)
[5] => Array
(
[0] => 2
[1] => 3
[2] => 8
)
[6] => Array
(
[0] => 2
[1] => 4
[2] => 7
)
[7] => Array
(
[0] => 2
[1] => 4
[2] => 8
)
)
Другие решения
Других решений пока нет …