PHP Permutation

Yes i had considered that, That will mean I have to complete all 20 first before I find the first 7 and also
that will also give me duplicates.

For example   start with a smaller number for simplicity sake 10 numbers and I want to find 7 out of 10

01234569870
01234567908

as you can see , both are unique combination, however the first 7 number are the same.

I am trying to get all posible permutations  for 7 out of 20 numbers available, and yet have 7 unique combinations for each  
 ( 20! )  possible combinations

Isnt there a much faster way to do this?

There are 2 main speed factors which may be slowing you down.  One, recursion might not be the best bet.  Recursion is usually not as efficient as looping, although it can reduce the amount of code you write.  The most optimal form of recursion (I forget the term for this) is where the recursive call is the last line in the function, so the interpreter can discard the state of the current function when it enters the next function.  This isn't the type of recursion you're using, however.  When you have a loop recursing down 20 levels several thousand times, things are bound to get slow...

Also, there is some (minor) overhead involved in method calls in PHP.  Changing from recursive calls to several nested loops should help trim some time off your function also.  Which is a shame, because your recursive method is nice and elegant, and doesn't use much code.

Hi Yuengling,

May I ask why the permutate function has this interesting implementation?  Is it important to preserve the order of the long numbers your script prints?  And also why the long numbers have double digits in them?  Is that important?  It does not make sense to have double digits in them because in your permutate function, these double digits would never be separated, and would not truly be permuated.

I think it'd be quite hard to design a flexible permutate function using purely loop.  This is one classic case where recursion should be used.

Cheers!

I think it's hard to be even faster as I used as simple as possible (unless someone did it using loop and still allow passing in the length of the number, which is not an easy task).  But please

BTW, I do think this algorithm, although not difficult, somehow deserves a bit more points (just so I could become top 15 in PHP this year earlier). :-)

Just realized two important things:
1. if all you care about is to permutate first 7 digits completely, DO NOT use your old version!  That one would be thousands times slower to permutate all 7 digits than my version even if string length is 10 digits long.
2. you should never use my solution to do anything like cracking passwords etc.  Thank you.

Here is a function that can work for you. I have not tested its speed put it should be higher than that of a recursive one.

function permutation($n) {
  $result = 1;
  if (!isset($k)) {
    $k = $n;
  }
  while($k--) {
    $result *= $n--;
  }
  return $result;
}

@inq123 : I've a proposition : we merge our loginnames and add our points :D

I'm sure the Mods, Admins, EE staff people will be happy ;-)

I'd be happy too, you have a lot more points than I do! :-)

BTW, Karitz, your permutation function's doing the permutation calculation P(n, k), while the OP asked for a function to display all the numbers that's permutated, meaning traverse through all the P(n, k) numbers (and potentially display each one).

BTW, sorry for always post immediately after I posted -- I always forget something before I press the "submit" button.

I asked OP whether the order of those numbers were important, but now I thought about it and think they can't be.  If they're important, then you're pretty much stuck at the one implementation OP presented, and there's not much room to improve there.  So it can't be important.

But one thing important that I semi-mentioned is that: OP's version can't be used for length longer than 10 unless modified, otherwise those double digit numbers will defeat the permutation.

Last thing: VGR, I thought Mods, etc. won't be happy to see our loginnames merged, that means there's only one volunteer to clean up and contribute! (although this one login might do more than before).

more than before... and be up 24 hours a day, and it's one member less, but a more active one.

An idea to elaborate :D

LOL...

BTW, sorry for slightly cluttering the thread.

By the way here are some fun factorial facts:
7! = 5040
20! = 2.4329e+18

So, calculating all combinations for 20 possible keys isn't really reasonable.  If you could find some algorithm to compute only the factorials which yeild a unique 7-digit number, I believe that would require (20! * 2) / ((1 + 20 - 7)!) combinations (guessing here).  And that gives you
2 * 20! / 14! = 55,814,400

This is starting to sound like a result set that might be too large to do very much with (?)

That said, here's a non-recursive algorithm for generating unique permutations of an array of values.  This should be faster than a recursive, but I haven't done time tests yet... (also, this doesn't do a substring of the resulting unique values, like first 7 chars of a 20-char permutation).

<?php

$length = 5; // length of the desired output string
$options = 5; // range of a single character in the output string

$lastComboIndex = $length-1;

$combo = array();
for ($i=0; $i<$length; $i++) {
        $combo[$i] = $i;
}

$trackingArray = array_fill(0, $lastComboIndex , 0);
echo join('-',$combo) . "<br />\n";
$matches = 1;
$dupCount = 0;
while (true) {
        for ($i=0; $i<=$lastComboIndex; $i++) {
                if ($trackingArray[$i] <= $i) {
                        $tmp = $combo[0];
                        $combo[0] = $combo[$i+1];
                        $combo[$i+1] = $tmp;
                        $trackingArray[$i]++;
                        while ($i-- > 0) $trackingArray[$i] = 0;
                        echo join('-',$combo) . "<br />\n";
                        $matches++;
                        break;
                }
                if ($i==$lastComboIndex - 1) {
                        echo "matches: $matches <br />\n";
                        die("DONE!");
                }
        }
}

?>

shmert, your function's buggy.  You need to check on it.  Here's the output of length=4:

0-1-2-3
1-0-2-3
2-0-1-3
0-2-1-3
1-2-0-3
2-1-0-3
3-1-0-2
1-3-0-2
0-3-1-2
3-0-1-2
1-0-3-2
0-1-3-2
2-1-3-0
1-2-3-0
3-2-1-0
2-3-1-0
1-3-2-0
3-1-2-0
0-1-2-3
1-0-2-3
2-0-1-3
0-2-1-3
1-2-0-3
2-1-0-3
matches: 24
DONE!

It's easy to see your function's wrong because there's no instance where 1 is in last digit.  please note that the only reason your matches is always right is that there're duplicates in your output.  See 2-1-0-3.  

BTW, I forgot to point out to you shmert that the original question was that take a length of 20 digits, permutate them and take only the first 7 digits.  That is different than permutate only 7 digits.  The function you provided is permutation in true sense (if bugs in your function are fixed), so was the original poster's solution.  But with the original question, really the first 7 digits of 20 numbers would be permutated in the sense that each digit will change from 0-9 (10^7 permutation, not 7!), and while your function and OP's solution both can do that too, they would do that (namely, permutate the first 7 digits from 0-9) millions of times of slower than my solution if length increases to 20.

But of course if OP modifies the question posed, the analysis would be different.

"shmert, your function's buggy.  " :D  no kidding ? Is that possible ? The Guru made a bug ? :D

inq123,
   I had the opportunity to test and use your code because it was faster, however the code are not of true permutation since there are duplicates, repeating of numbers in each string, so I added a second function that would filter out the duplicates.  The result are stored into the database so that I would only have to run the script once and the result will always be the same so retrieving it from the database would be much faster than doing the permutation everytime.

   I previously was going to go with the code i had made, but it seems to freeze up the apache server once it got to 8 digits permutation, frustrated by the crashing of the apache server (I'm running the script on my personal computer), I switch over to your code thinking that I would not encounter this crashing, but then I noticed that it does the same thing when it reach 8 digits permutation on your code.

   Now, thinking that its must not be the script thats doing it, it must be the configuration problem in either php or apache. I then proceeded to increase the size of memory allowed for a script to 256 mb and increased the length of time executed to 4 hours in php configuration file. I also then went and configure the apache file to allow 4 hours before timeouts, and increased the size of process allowed to 1000.  (The computer is 2.4 ghz with 1gb ram)  And restarted the apache server. I shut down all other programs to allow only just the script to run. I still encounter this same crashing down of the apache server when it encounters 8 digits to permutate and getting only the length of 5 or 6 characters.

Anyone know why it does this ? I've increased the number of points to 320, that also includes the 20 points in the other posting.

If it matters, the database table structure have 9 field, and each field are just a character of length 2 and are as the following

table
----------------
perm, take, a1, a2, a3, a4, a5, a6, a7

i've limits the length of string from 3 up to 7 characters.


The code are as following.....including the filtering out of duplicates.
---------------------------------------------------------------------------------------
<?
      include ('courses_db.php');

       $numbers =Array();
       $perm =Array();
       $length =0;
      $num =0;
      $get =0;
      main();

/*-------------------------------------------------------------------------*/

      function permutate($n)
      {
            global $numbers, $perm, $length, $num, $get;

            for($i = 0; $i < $num; $i++){
                  $numbers[$n - 1] = $i;
                  if($n == 1){
                      for($j = 0; $j < $length; $j++){
                            $perm[$get][$j] =$numbers[$j];
                           }
                               $get++;
                         }
                         else{
                            permutate($n - 1);
                         }
                 }
       }

/*-------------------------------------------------------------------------*/
      function filter()
      {
            global $perm;
            $unique =Array();
            $filter =Array();
            $index =0;

            $size =count($perm);
            for($i =0; $i < $size; $i++){
                  $unique =$perm[$i];
                  $count =count($unique);
                  $fail =TRUE;
                  for($n =0; ($n < $count && $fail); $n++){
                        $x =$unique[$n];
                        for($j =0; ($j < $count && $fail); $j++){
                              if($x ==$unique[$j] & $j != $n){
                                    $fail =FALSE;
                              }
                        }
                  }
                  if($fail ==TRUE){
                        $filter[$index] =$unique;
                        $index++;
                  }
            }
            $perm =$filter;
      }

/*-------------------------------------------------------------------------*/
      function debug()
      {
            global $perm;
            $take =$perm;
            $x =count($take);

            for($i =0; $i < $x; $i++){
                  $cell =count($take[$i]);
                  for($n =0; $n < $cell; $n++){
                        echo $take[$i][$n];
                  }
                  echo "<BR>\n";
            }
      }
/*-------------------------------------------------------------------------*/
      function permToDB()
      {
            global $perm, $length, $num;
            global $table_perm;

            $array =$perm;
            $size =count($array);


            for($i =0; $i < $size; $i++){
                  $set ="perm, take,";
                  $insert ="\"$num\",\"$length\",";
                  $cell =count($array[$i]);

                  for($n =0; $n < $cell; $n++){
                        $set    .="a".($n + 1);
                        $insert .="\"".$array[$i][$n]."\"";

                        if (($n + 1) != $cell){
                              $set         .=",";
                              $insert .=",";
                        }
                  }
                  $query ="INSERT INTO $table_perm ($set) VALUES ($insert)";
                  mysql_query($query) or die("<BR><BR>".mysql_error(). " - ". $query);
            }
      }

/*-------------------------------------------------------------------------*/
      function main()
      {
            global $length, $num, $get;

            for($length =3; $length <= 7; $length++){
                  for($num =$length; $num < 10; $num++){
                        echo "length: $length....finding up to $num numbers<BR>";
                        $get =0;
                        permutate($length);
                        filter();
                        //permToDB();
                        debug();
                        //echo "<BR><BR>";
                  }
            }
      }

?>

Note: there's an optional argument to specify a startIndex in the function.  That is because if you try to do all 20 at once, the machine will choke.  Factorials get large very very quickly.  I think 50! is greater than the number of atoms in the universe.  You will need a more robust CPU for that one ;)

I think if you take the first 7 characters from all permutations of 20 characters, you will end up with 20!/13! options, or 390,700,800.  That's rather a lot.  If you do multiple passes with the startIndex set differently each time, this may end up working for you.

I must admit I'm rather curious what you intend to do with this very large array of permutations.  It would be pretty simple to convert the function I posted above to get the Nth permutation, instead of returning the entire list.  Would that be useful?

Yuengling, please see this post of mine above:

================
BTW, I forgot to point out to you shmert that the original question was that take a length of 20 digits, permutate them and take only the first 7 digits.  That is different than permutate only 7 digits.  The function you provided is permutation in true sense (if bugs in your function are fixed), so was the original poster's solution.  But with the original question, really the first 7 digits of 20 numbers would be permutated in the sense that each digit will change from 0-9 (10^7 permutation, not 7!), and while your function and OP's solution both can do that too, they would do that (namely, permutate the first 7 digits from 0-9) millions of times of slower than my solution if length increases to 20.

But of course if OP modifies the question posed, the analysis would be different.
================

So as you see this is why my version have the duplicate numbers you mentioned.  In fact, in your version where you permutate 20 numbers concatenated together, you'll have duplicate numbers in the first 7 digits that you want if you wait long enough (print out more than 10! numbers and you'll find those).  True permutation with 10-based integers and printed out the way your script did would only work on length of maximum of 10 digits.  That's why I made my version, and that's why mine could be thousands times faster if we imitate true permutation of 20 numbers but only take the first 7 digits.  That was your original question.

> But inq, I think it's closer to the solution than yours, which simply iterates through sequentially.

shmert, you seems to be always on the run and hardly had time to read and understand others' posts.  Please see here (old post plus a little expansion):

++++++++++++++++++++++++++++++++++++++

================
BTW, I forgot to point out to you shmert that the original question was that take a length of 20 digits, permutate them and take only the first 7 digits.  That is different than permutate only 7 digits.  The function you provided is permutation in true sense (if bugs in your function are fixed), so was the original poster's solution.  But with the original question, really the first 7 digits of 20 numbers would be permutated in the sense that each digit will change from 0-9 (10^7 permutation, not 7!), and while your function and OP's solution both can do that too, they would do that (namely, permutate the first 7 digits from 0-9) millions of times of slower than my solution if length increases to 20.

But of course if OP modifies the question posed, the analysis would be different.
================

So as you see this is why my version have the duplicate numbers you mentioned.  In fact, in your version where you permutate 20 numbers concatenated together, you'll have duplicate numbers in the first 7 digits that you want if you wait long enough (print out more than 10! numbers and you'll find those).  True permutation with 10-based integers and printed out the way your script did would only work on length of maximum of 10 digits.  That's why I made my version, and that's why mine could be thousands times faster if we imitate true permutation of 20 numbers but only take the first 7 digits.  That was your original question.

+++++++++++++++++++++++++++++++++++++++++++++++

The OP actually modified the behavior expected of the program (namely OP originally said 20 numbers, permutate, take first 7 digits, now OP meant true permutation of only 7 digits, those are two very different things, neither OP or you seemed to have realized that).  But I do agree, and anticipated, that if OP modifies the question, then it would be different, and I said long time ago your version, if fixed, is true permutation.

> I think if you take the first 7 characters from all permutations of 20 characters, you will end up with 20!/13! options, or 390,700,800.  That's rather a lot.  If you do multiple passes with the startIndex set differently each time, this may end up working for you.

That's right.  I just want to add that in OP's original version those 20 characters have only 10 variations, thus the old version ended up with 10^7, less than you would expect.

Besides, I don't see why the server would choke because of that at all.  Notice the OP's old version did not store anything in memory and thus however many numbers would not have mattered.  The stack initiation and destroy would allow them reused.  I see no problem there.  There must be some other problem.

Yuengling,

I just had some time and thought about it -- if what you need is true permutation, then your version of recursive is the way to go.  I tried to produce a different one and ended up with almost exactly the same version as yours!  For faster version of true permutation, you probably have to use shmert's provided non-recursive versions, if the 2nd version fixed bug.

As to your server's problem, for both my version and your initial version, there was no storage of anything and should not have used up memory.  Did you use top to monitor memory usage?  That should help diagnosis.

Good luck!

inq, I actually did read your post, and it didn't seem like your iterative algorithm addressed the initial question, which explicitly stated he was looking for "permutations"...  That said, it's confusing how things will behave once you get past 9, into double-digits.

My code is not the most efficient way to go if you are only getting the first unique 7 characters from a 20-character permutation.  It relies on array_unique() for that, which is going to bomb, since as inq pointed out you want this to run without taking up memory.

The correct way to do this would be to find all combinations for 7 digits out of 20 (resulting in 77,520 combinations, I think), then run my algorithm on each of those possible combinations (7! each), which will give you 390,700,800 final unique combinations.

I'm creating a program for a local college, I've gathered all possible courses offered by that college and stored it into MySQL database.

What I was trying to do, is to create a web application that would allow a student to choose several courses they may wishes to take say they may be interested in 8 classes, but want to take only 5 courses, and all of them have to be after 12(noon) only.

What I had done was to get all courses that the student had wanted to take and stored it in an array.

This is where permutaion comes in, to get the permutation of indexs in an array  

for example,

courses [1] ="Math 8am - 9am"
courses [2] ="Math 1pm - 3pm"
courses [3] ="Chemistry 3pm - 4pm"
courses [4] ="Chemistry 11am - 1pm"
courses [5] ="Database 5pm - 6pm"
courses [6] ="Gym 6pm - 7pm"
courses [7] ="Science 2pm - 3pm"
courses [8] ="Science 4pm - 5pm"


Now, the possible courses may be

courses[2], courses[3], courses[5], courses[8],
and so forth without any courses having a conflict in time.

Now, a permutation of 20 would be ridiculous and i doubt a student would pick that many so i would not even go that far. However I will go up to permutation of 10 numbers, of which a student may select 3 to 7 courses.
That would be ( [3 to10]! / (10 - [3 to 7] )!

But trying to get the permutation working and store all possibility into the database has been an hassle, apache freezing up on me, trying to install each permutation individually so that it would not overwhelm apache server, but to no avail. Apache just decide to shut down and become a cry baby.

If you have a much better idea then it would be greatly appreciated.

the permutation will be use to find indexes in an array.

AH, worked all week on making the permutation work,  I can see that it will be futile.  I only have a 30 second window on my web hosting space to run the script and permutation will just eat up all of it.

I've decided to go with combination algorithm, achieving only just the unqiue number where order does not matter.

I will award points by the end of the week if anybody is willing to come up with a combination code, otherwise I'll just split the points between schmert and inq.  I thank you for your time and effort.

all right.  I don't have any new ideas for this :-/  good luck!