Very fast permutations in PHP

Question

I have searched the internet in great detail and found many samples of PHP scripts that are addressing permutations. All these scripts are ok for permuting a few numbers and a few words here and there but when we get to perform some heavy stuff I can't execute the code.

Here is the essence of the thing we need and things I did.

I have to find all unique combinations of a range of numbers from 1 to 8. I do this easily,, no problems there...

Then I have to permute each combination which should result with a crazy number results,, and then I have to perform string replacements on each result...

I know this is intense,,, and I do manage to get it done with numbers up to 6.

6 Executes pretty slow,, and 7 and 8 simply mess with the memory allocation on the machine.

My primary question is

Is there a way I can do permutations super fast? Preferably without affecting memory too badly... AND how fast can in PHP realistically a few million records be displayed (doing it in command line,,, browser doesn't matter here)

Would something like Rainbow Tables help? http://en.wikipedia.org/wiki/Rainbow_table — Stephen O'Flynn, Oct 13 '12 at 09:03
If command line is an option and browser doesn't matter, I'm sure there's better tools to do this than PHP. — BudwiseЯ, Oct 13 '12 at 09:12
I do agree with you budwiser. I seriously need to find this as fast as possible fror PHP however, although I DO want to see a very fast C code if someone has it too. — GRowing, Oct 13 '12 at 09:14
The issues is really getting the best optimized algorithm possible. I can't find a single sample that even does it in a straight forward elegant way let alone a fast one. — GRowing, Oct 13 '12 at 09:15
If you are looking for performance don't do it in PHP. May I ask why you need to do this? What is your use case? — PeeHaa, Oct 13 '12 at 09:40
Where is it being slowed down? Is it the finding of the permutations or the string handling? Is it recursive? Can you pre-load solutions ahead of time and use a look-up? — Stephen O'Flynn, Oct 13 '12 at 09:42

HamZa · Accepted Answer · 2012-10-13T09:36:08.097

I don't know if this will be helpful, but i already made a script that generates the permutation of 10 numbers (0 -> 9) in lexicographic order, and it runs in ~60sec [Quadcore 2.7Ghz] and uses 512MB due to the array sizes ...

By mathematical calculations: 10! = 3628800 permutations in 60 sec, 8! = 40320 permutations, so it should run in (60 * 40320) / 3628800 = 0.67sec say 1 second ! You may need to change the code for a 8-number permutations! PS: I don't know if the browser would handel the output of +3M numbers !

<?php

/* 0 - > 9 PERMUTATION SCRIPT */
ini_set('memory_limit', '512M');
ini_set('max_execution_time', '0');

$st = timer();


$permutations = array();

for($a=0;$a<=9;$a++){
    for($b=0;$b<=9;$b++){
        if($b != $a){
            for($c=0;$c<=9;$c++){
                if($c != $a && $c != $b){
                    for($d=0;$d<=9;$d++){
                        if($d != $a && $d != $b && $d != $c){
                            for($e=0;$e<=9;$e++){
                                if($e != $a && $e != $b && $e != $c && $e != $d){
                                    for($f=0;$f<=9;$f++){
                                        if($f != $a && $f != $b && $f != $c && $f != $d && $f != $e){
                                            for($g=0;$g<=9;$g++){
                                                if($g != $a && $g != $b && $g != $c && $g != $d && $g != $e && $g != $f){
                                                    for($h=0;$h<=9;$h++){
                                                        if($h != $a && $h != $b && $h != $c && $h != $d && $h != $e && $h != $f && $h != $g){
                                                            for($i=0;$i<=9;$i++){
                                                                if($i != $a && $i != $b && $i != $c && $i != $d && $i != $e && $i != $f && $i != $g && $i != $h){
                                                                    for($j=0;$j<=9;$j++){
                                                                        if($j != $a && $j != $b && $j != $c && $j != $d && $j != $e && $j != $f && $j != $g && $j != $h && $j != $i){
                                                                            $permutations[] = $a.$b.$c.$d.$e.$f.$g.$h.$i.$j;
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

echo count($permutations);


$et = timer();
$time = $et - $st;
echo "<br/>in : ".$time." seconds.";
function timer(){
    list($usec, $sec) = explode(" ", microtime());
    return((float)$usec + (float)$sec);
}

?>

EDIT: 1->8 permutation script in: ~0.43 seconds.

<?php
$permutations = array();

for($a=1;$a<=8;$a++){
    for($b=1;$b<=8;$b++){
        if($b != $a){
            for($c=1;$c<=8;$c++){
                if($c != $a && $c != $b){
                    for($d=1;$d<=8;$d++){
                        if($d != $a && $d != $b && $d != $c){
                            for($e=1;$e<=8;$e++){
                                if($e != $a && $e != $b && $e != $c && $e != $d){
                                    for($f=1;$f<=8;$f++){
                                        if($f != $a && $f != $b && $f != $c && $f != $d && $f != $e){
                                            for($g=1;$g<=8;$g++){
                                                if($g != $a && $g != $b && $g != $c && $g != $d && $g != $e && $g != $f){
                                                    for($h=1;$h<=8;$h++){
                                                        if($h != $a && $h != $b && $h != $c && $h != $d && $h != $e && $h != $f && $h != $g){
                                                            $permutations[] = $a.$b.$c.$d.$e.$f.$g.$h;
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

echo count($permutations);
?>

Unusual code. Thank you. I will compare what I have with this and see how it would work for me. Yours, with print_r of array executed in 0.47 for me. I will definitely look deeper into this. Considerable improvement compared to what I have. I wonder if there is a cleaner way to write it. — GRowing, Oct 13 '12 at 10:38
oh,, browser doesn't matter for my need,, I am outputting it to CMD — GRowing, Oct 13 '12 at 10:39
"cleaner" there is certainly one there, but i already spent hours on "optimizing" this code, you may "compress" the code by deleting spaces etc... btw in C++ there is a function called "next_permutation()" it may help you, so good luck ! — HamZa, Oct 13 '12 at 12:34
By cleaner I meant,, I can\t used a FIXED range of 8. I have to be able to determine the range 1 to n, while N can't be bigger than 8. Your code works really, really well, thank you :) Now I have to find a way to dynamically alter it. — GRowing, Oct 13 '12 at 22:41
I mean,, to alter it enough so that it is scalable for variable input — GRowing, Oct 13 '12 at 22:46

Very fast permutations in PHP

1 Answers1