PHP: используя слишком много вложенных циклов, ищем более эффективное решение - PullRequest
Новая
       34

PHP: используя слишком много вложенных циклов, ищем более эффективное решение

0 голосов
/ 14 октября 2018

Мой сценарий сосредоточен вокруг массива $givenNumbers со случайным количеством случайных чисел от 1 до 1000: 

$givenNumbers = [383, 886, 777, 84, 327, 336, 505, 846, 729, 313, 857, 124, 895, 582, 545, 814, 367, 434, 364, 43, 750, 87, 808, 276, 178, 788, 584, 403, 651, 754, 399, 932, 60, 676, 368, 739, 12, 226, 586, 94, 539, 654, 999, 5, 24];

Массив отсортирован и все повторения элементов удалены: 

 $givenNumbers = array_unique($givenNumbers);
 sort($givenNumbers);

Затем я объявляю переменную $amount, представляющую собой количество элементов в $givenNumbers; 

$amount = count($givenNumbers);

Теперь я сохраняю все возможные фрагменты массива в массиве $slices, используяциклы: 

$slices = [];
for ($i = 0; $i < $amount; $i++) {
        for($j = 0; $j < $amount; $j++) {
            array_push($slices, array_slice($givenNumbers, $i, $j));
        }
    }

Сохраняя все фрагменты в $slices Я хочу найти все возможные комбинации из десяти фрагментов, которые, если объединить вместе, будут содержать все элементы $givenNumbers, при этом ни один элемент не появится дважды или более.

Я пытался сделать это, циклически переключая ключи slices: 

$combinations[]
for($i = 0; $i < $amount; $i++) {
        for($j = $i+1; $j < $amount; $j++) {   
            for($k = $j+1; $k < $amount; $k++) {
                for($l = $k+1; $l < $amount; $l++) {
                    for($m = $l+1; $m < $amount; $m++) {
                        for($n = $m+1; $n < $amount; $n++) {   
                            for($o = $n+1; $o < $amount; $o++) {
                                for($p = $o+1; $p < $amount; $p++) {
                                    for($q = $p+1; $q < $amount; $q++) {
                                        for($r = $q+1; $r < $amount; $r++) {

                                            $combStorer = [];
                                            $placeholder = array_merge($slices[$i], $slices[$j], $slices[$k], $slices[$l], $slices[$m], $slices[$n], $slices[$o], $slices[$p], $slices[$q], $slices[$r]);
                                            $placeholder = array_unique($placeholder);
                                            if (count($placeholder) == $amount) {
                                                    array_push($placeholder, $slices[$i], $slices[$j], $slices[$k], $slices[$l], $slices[$m], $slices[$n], $slices[$o], $slices[$p], $slices[$q], $slices[$r]);
                                                    foreach ($placeholder as $comb) {
                                                    $combStorer[] = $comb;
                                                }
                                                $combinations[] = $combStorer;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

Это должно в основном найти все комбинации из десяти массивов в slices, которые соответствуют моему требованию и хранилищуих в виде многомерного массива в $combinations.

Однако, когда я открываю свой предварительный просмотр в реальном времени, я получаю фатальную ошибку, так как было превышено максимальное выполнение 30 секунд.

Several Пользователи обратили мое внимание на то, что этот метод слишком запутанный и что определенно есть лучшее решение.

Кто-нибудь может предложить более эффективное решение?

1 Ответ

0 голосов
/ 14 октября 2018

Это не бесконечно, это просто очень очень большое количество итераций, в основном: 

(amount ^ 10) / 2

Это очень быстро нарастает, например, для увеличениязначения для amount: 

$ time php index.php 5

real    0m0.067s
user    0m0.043s
sys     0m0.023s
$ time php index.php 10

real    0m0.061s
user    0m0.046s
sys     0m0.014s
$ time php index.php 15

real    0m0.117s
user    0m0.096s
sys     0m0.012s
$ time php index.php 20

real    0m0.546s
user    0m0.506s
sys     0m0.030s
$ time php index.php 25

real    0m3.245s
user    0m3.204s
sys     0m0.032s
$ time php index.php 30

real    0m24.624s
user    0m24.129s
sys     0m0.032s
$ time php index.php 35

real    1m55.215s
user    1m54.532s
sys     0m0.029s
...