# Thread: permutations - recursive function needs speed increase

1. ## permutations - recursive function needs speed increase

I'm currently working on a sudoku puzzle class that will (hopefully) be able to solve ANY sudoku puzzle...yeah, i'm a little bored....

Everything is working to this point, but I've run into a speed bump with a function I wrote to get all possible permutations of a multi-dimensional array. The function works, but it is ssssslllllooooowwww.....
It works great on small md-arrays, but on an array with 10000 possible permutations (for example) it takes about 1/4 of a second.

With literally millions of permutations to calculate, this obviously isn't going to work....not to mention that I will probably be facing some memory problems here soon.

Here is the function (an excerpt from the class)....If anyone has any ideas to speed it up I would love to hear them. Recursion seemed the most obvious solution to this problem, and honestly I'm not sure how to approach this in another way:

PHP Code:
```                   /*    -- get all the possible permutations for a multidimensional array. --                   \$mdArray should be a multi-dimensional array like so:                           array(                   array('a1', 'a2', 'a3'),                   array('b1', 'b2'),                   array('c1', 'c2', 'c3', 'c4'),               );     */                  function getAllPermutations(\$mdArray, \$firstTime=true, \$tempArray=array()) {                          // initialize results array               if (\$firstTime) { \$this->permutationsResultsArray = array(); }                          // find first sub array and iterate through it               \$thisArray = array_shift(\$mdArray);                      foreach (\$thisArray as \$key => \$elem) {                   \$tempArray[] = \$elem;                                      if (count(\$mdArray) == 0) {                 \$this->permutationsResultsArray[] = \$tempArray;                   } else {              \$this->getAllPermutations(\$mdArray, false, \$tempArray);                   }                   array_pop(\$tempArray);                                  }                  }  ```
thanks for any advice on this....

[ edit ]

after posting this, I realized a severe inefficiency in the function: since in a sudoku puzzle each number (1-9) can only be used once per row, column, and "sector", I don't actually need EVERY permutation, just the ones that contain unique combinations. changing the function to this sped it up about 40x:

PHP Code:
```       function getAllPossiblePermutations(\$mdArray, \$firstTime=true, \$tempArray=array()) {                // initialize results array          if (\$firstTime) { \$this->permutationsResultsArray = array(); }                // find first sub array and iterate through it          \$thisArray = array_shift(\$mdArray);            foreach (\$thisArray as \$key => \$elem) {                       // if this number has already been used, skip this possible permutation              if (in_array(\$elem, \$tempArray)) { continue; }                            \$tempArray[] = \$elem;                            if (count(\$mdArray) == 0) {                 \$this->permutationsResultsArray[] = \$tempArray;              } else {              \$this->getAllPossiblePermutations(\$mdArray, false, \$tempArray);              }              array_pop(\$tempArray);                        }        }  ```
i'm still looking for a faster algorithm though, if anyone can help....

2. Umm...

PHP Code:
``` // ... // initialize results array           if (\$firstTime) { \$this->permutationsResultsArray = array(); }  ```
Well you could remove the need for this, and instead class this class method first, to initialise the algorithm, and then instead of recursing from within this class method, recurse to a secondary class method, which basically does the same thing yes?

So, you can execute the first recursive class method to act as the catalyst, and from there, continue the recursion from the secondary class method, which therefore returns the results for you.

Also, is there not a way to remove the temp. store? If you could remove that as well, then that may help.

3. The best way to optimize speed of recursive algorithms, is to remove the
recursion. This is easily done with a while loop and an array that emulates
the callstack.
I've also done some more subtle optimizations like the isset() vs. count() and
redundant negation. This version is two times faster now.
The code looks a litte bit ugly but i hope you get the idea.

Of course optimizing the algorithm logic could bring up more performance,
but thats too much for a rainy sunday.

PHP Code:
```     function getAllPossiblePermutations2(\$MdArray, &\$Result, &\$TempArray=array())     {         \$stack = array(array(\$MdArray, &\$Result, &\$TempArray));         while (\$arg = array_pop(\$stack))         {             \$mdArray =& \$arg[0];             \$result =& \$arg[1];             \$tempArray =& \$arg[2];             \$thisArray = array_shift(\$mdArray);             foreach (\$thisArray as \$elem)             {                 if (in_array(\$elem, \$tempArray))                     continue;                 \$tempArray[] = \$elem;                 if (isset(\$mdArray[0])) {                     \$stack[] = array(\$mdArray, &\$result, &\$tempArray);                 } else {                     \$result[] = \$tempArray;                 }                 array_pop(\$tempArray);             }         }     }  ```

4. thanks for the help guys....

Dr. Livingston--
I did notice a small speed increase removing the boolean and using 2 class methods. unfortunately i can't get rid of the tempArray, as that's where each permutation is stored. I appreciate the help.

elias--
I tried your way (very nice btw--it never occured to me that you could fake recursion like that), but didn't notice a 2x speed difference....using isset() instead of count() made a noticable difference, but when the functions were identical with 1 using recursion and one without, the speeds were pretty much identical.

5. Originally Posted by aamonkey
but when the functions were identical with 1 using recursion and one without, the speeds were pretty much identical.
Yes this happens if you don't have much to "recurse". With your example
array from above you'll not gain much performance, but if you extend it
like this:

PHP Code:
``` array(      array('a1', 'a2', 'a3'),      array('b1', 'b2'),      array('c1', 'c2', 'c3', 'c4'),      array('d1', 'd2', 'd3', 'd4'),      array('e1', 'e2', 'e3', 'e4'),      array('f1', 'f2', 'f3', 'f4'), );  ```
the non-recursive version will speed up. Here is a small benchmark to see the proportions.

Code:
```//your example array
1 - 0.000317
2 - 0.000241

//extended array
1 - 0.016237
2 - 0.008070```

6. I've probably screwed up something in your code then....I've been testing on an array with 30,000+ possible permutations, and I was getting some errors / incorrect results, so I modified the code to this:

PHP Code:
```       \$tempArray = array();      function getAllPossiblePermutations2(\$mdArray, &\$result, &\$tempArray) {                         \$stack = array(array(\$mdArray, &\$result, &\$tempArray));                      while (\$arg = array_pop(\$stack)) {                              \$mdArray =& \$arg[0];               \$result =& \$arg[1];               \$tempArray =& \$arg[2];               \$thisArray = array_shift(\$mdArray);                  foreach (\$thisArray as \$elem) {                   if (in_array(\$elem, \$tempArray)) { continue; }                                      \$tempArray[] = \$elem;                   if (isset(\$mdArray[0])) {                  \$stack[] = array(\$mdArray, &\$result, \$tempArray);                   } else {                       \$result[] = \$tempArray;                   }                   array_pop(\$tempArray);           }       }   }  ```
I couldn't get the function argument "&\$tempArray=array()" to work -- I kept getting an "unexpected '(' in line [ function line]" error. I think I read something about this being available in php 5, unfortunately I'm still stuck on vs. 4. Also, when I used the line
PHP Code:
```    \$stack[] = array(\$mdArray, &\$result, &\$tempArray);  ```
the function did not work...it worked when I removed the \$temparray reference (as in code above), but I'm not seeing the speed increase...

7. Originally Posted by aamonkey
I couldn't get the function argument "&\$tempArray=array()" to work -- I kept getting an "unexpected '(' in line [ function line]" error. I think I read something about this being available in php 5, unfortunately I'm still stuck on vs. 4.
Oh yes i'm runnning php5.2dev here and have no php4.

Originally Posted by aamonkey
but I'm not seeing the speed increase...
Edit:

Two mistakes:
- benchmarked versus your first implementation
- wrong results

Now i've got almost the same performance with recursive and non recursive
versions too. Well, the latter will never smash on recursion limits.

8. Originally Posted by aamonkey
i'm still looking for a faster algorithm though, if anyone can help....
There was a competition here to write a sudoku solver, it's all open ssource so you can see quite a few ways people have tried to do it if you want some ideas.

Douglas

9. thanks DougBTX,

if only I could read Ruby....

I did manage to wade my way through a few scripts and got a couple ideas off of that.

That site is great, btw....almost makes me want to convert to Ruby just to participate (if only there were a php equivalent!)--thanks much for the link

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•