Перестановки / комбинации на переполнение стека
Я пытаюсь сделать скрипт для выполнения всех перестановок / комбинаций для 6 чисел от 0 до 45, без повторений, но он не работает, потому что некоторые числа повторяются в одной строке.
Что я делаю не так?
КОД:
for($a=0; $a<45-5; $a++)
for($b=$a+1; $b<45-4; $b++)
for($c=$b+1; $c<45-3; $c++)
for($d=$c+1; $d<45-2; $d++)
for($e=$d+1; $d<45-1; $d++)
for($f=$e+1; $d<45; $d++)
echo "$a $b $c $d $e $f \n";
Я тестирую другой код, но получаю эту ошибку:
Неустранимая ошибка: допустимый объем памяти 33554432 байта исчерпан (попытка выделить 2348617 байтов)
<?php
function permutations($arr,$n)
{
$res = array();
foreach ($arr as $w)
{
if ($n==1) $res[] = $w;
else
{
$perms = permutations($arr,$n-1);
foreach ($perms as $p)
{
$res[] = $w." ".$p."<p>";
}
}
}
return $res;
}
$words = array('00','01','02','03','04','05','06','07','08','09','10','11','12','13','14','15','16','17','18','19','20','21','22','23','24','25','26','27','28','29','30','31','32','33','34','35','36','37','38','39','40','41','42','43','44','45');
$pe = permutations($words,6);
print_r($pe);
?>
Что я делаю не так?
Спасибо
Решение
Ваша первая программа имеет несколько опечаток: циклы for для $e а также $f содержать $d, Если я изменю это, вывод этой программы выглядит нормально для меня. Находит 8145060 перестановок.
Ваши вторые решения работают с рекурсией, которая явно слишком глубоко вложена, поэтому она исключает память, которую вы имеете.
Другие решения
PHP использует минимум 72 байта памяти для каждой переменной, 8 миллиардов результатов потребуют около 600 гигабайт оперативной памяти. PHP7, иначе PHPNG уменьшает это до 56 байт, но это не очень поможет в вашей ситуации. Даже на скомпилированном языке это было бы большим.
Когда в прошлом я делал комбинации слов, в которых требовалось много результатов, я заканчивал тем, что записывал их в файл, поэтому он обрабатывает порции данных и записывает в файл партиями. Это более сложный код, но он необходим для таких вещей.
Еще одна вещь, которую вы можете сделать для работы с большими наборами данных: если вам не нужны все они легко доступны и могут работать в блоках, вы можете json кодировать наборы массивов, так что это не приводит к накладным расходам на каждую переменную. В вашем случае, однако, это все равно будет бесполезно.
Похоже, у вас разрешено PHP 32 МБ ОЗУ, если это контролируемая среда, вы можете вызвать:
ini_set('memory_limit','256M');
установить максимальный объем памяти текущего скрипта. Тем не менее, вам не хватит памяти, и вам потребуется рефакторинг кода.
Это сгенерирует все перестановки (не комбинации):
$words = array("00", "01", "02", "03", "04");
pick($words, 3);
function pick($words, $num, $picked = array()) {
for ($i = 0; $i < count($words); $i += 1) {
$word = $words[$i];
$remaining_words = array_diff($words, array($word));
if ($num > 1) {
// pick the remaning $num-1 words
pick(array_values($remaining_words), $num - 1, array_merge($picked, array($word)));
} else {
echo implode(",", array_merge($picked, array($word))) . "\n";
}
}
}
Это выбирает n слова из m варианты, чтобы вы получили m! / (m-n)! Результаты. За n=3 а также m=5 ты получаешь 60, 45!/39! дает 5,864,443,200,
Поскольку вы хотите вывод как csv, вы можете изменить его:
$handle = fopen("perms.csv", "w");
// code
// instead of echo:
fputcsv($handle, array_merge($picked, array($word)));
// end code
fclose($handle);
Это не должно потреблять много памяти вообще. Это будет иметь верхний предел $num*$words элементы, которые должны быть хорошо под 1mb (глубина первая хороша, ширина сначала ужасна). Теперь выходной файл будет огромным: P
Я понятия не имею, сколько времени потребуется для создания этого файла. Я рекомендую вам провести несколько тестов. Вам скорее всего понадобится set_time_limit(0); дать вашему сценарию неограниченное время, но сначала поэкспериментируйте с более низкими значениями (или будьте готовы убить сценарий). Могут быть способы сделать это быстрее, часть логики массива не особенно быстра.