PHP: Using too many nested loops, looking for a more efficient solution

Question

My script is centred around the array $givenNumbers with a random amount of random numbers from 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];

The array is sorted and all repetitions of elements are removed:

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

I then declare the variable $amount which is the amount of elements in $givenNumbers;

$amount = count($givenNumbers);

I now store all possible slices of the array in the array $slices by using loops:

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

Having stored all slices in $slices I want to find all possible combinations of ten slices which, if merged together, will contain all elements of $givenNumbers without any element appearing twice or more.

I tried to do this by looping through the keys of 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;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

This should basically find all combinations of ten arrays in slices which meet my requirement and store them in the form of a multidimensional array in $combinations.

However, when I open my live preview, I get a fatal error, since the maximum execution of 30 seconds has been exceeded.

Several users have brought to my attention that this method is too convoluted and that there is definitely a better solution.

Could anyone suggest a more efficient solution?

What makes you say the loop must be infinite? The inner loop will run a number of times equal to $amount to the power of 10. Even if $amount is just 2, that is 1024 times. If $amount is 3, it will run 59,049 times. For bigger values this will increase vastly. So it is hardly surprising that your script is timing out, and not surprising at all that removing a couple of the loops (so it only runts n^8 times instead of n^10) makes a huge difference. You need to find a more efficient way of doing whatever it is that you are trying. — Robin Zigmond
– Robin Zigmond, Commented Oct 14, 2018 at 11:40
It can happen that loop is not infinite, but just long enough to be greater than 30 seconds. Decrease $amount and check. — u_mulder
– u_mulder, Commented Oct 14, 2018 at 11:40
Provide the $amount value. Also, try to increase the execution time. — Oliver Tušla
– Oliver Tušla, Commented Oct 14, 2018 at 11:41

msbit · Accepted Answer · 2018-10-14 11:58:47Z

1

It's not infinite, it's just a very very large number of iterations, basically:

(amount ^ 10) / 2

That ramps up extremely quickly, e.g, for increasing values for 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

answered Oct 14, 2018 at 11:58

msbit

4,4332 gold badges12 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

PHP: Using too many nested loops, looking for a more efficient solution

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related