Page 1 of 1

combinatoric

Posted: Tue Aug 09, 2011 7:21 am
by turbo535
Hello guys, I have script:

Code: Select all

<?php
    
    function Permutate($strDataIn, $Length, &$PermutateCount) {
        for ($i = 0; $i < strlen($strDataIn); $i++) {
            $PermArray[0][$i] = substr($strDataIn, $i, 1);
            $temp[$i] = substr($strDataIn, $i, 1);
            $temp2[0][$i] = substr($strDataIn, $i, 1);
        }
        for ($i = 1; $i < $Length; $i++) {
            for ($k = 0; $k < strLen($strDataIn); $k++) {
                for ($j = 0; $j < sizeof($temp2[$i - 1]); $j++) {
                    $PermArray[$i][($k * sizeof($temp2[$i - 1])) + $j] = $temp[$k] . $temp2[$i - 1][$j];
                    $temp2[$i][($k * sizeof($temp2[$i - 1])) + $j] = $temp[$k] . $temp2[$i - 1][$j];
                }
            }
        }
        $k = 0;
        for ($i = 0; $i < $Length; $i++) {
            $k += sizeof($PermArray[$i]);
        }
        $PermutateCount = $k;
        return $PermArray;
    }
    $StartString = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    $len = 4;
    $Return = Permutate($StartString, $len, $cnt);
    print "Returned <b>$cnt</b> permutations.<br><hr>";
    for ($i = 0; $i < $len; $i++) {
        for ($j = 0; $j < sizeof($Return[$i]); $j++) {
            print $Return[$i][$j] . "<br>";
        }
        print "<br>";
    }
    ?>
How to change this script that would return only unique combinations and only combinations of 4 charters, not 1, 2 or 3? I mean I need only AAAA combinations not AAA, AA. Thank you.

Re: combinatoric

Posted: Tue Aug 09, 2011 8:17 am
by Dodon
I modified you code a bit and that should do the trick. Keep in mind your code takes a while to run, and having larger input strings makes it take longer and longer. You can optimize your own code yourself, that's not something I'm going to do :)

This should do the trick for now:

Code: Select all

<?php

    function Permutate($strDataIn, $Length, &$PermutateCount) 
    {
        for ($i = 0; $i < strlen($strDataIn); $i++) 
        {
            $PermArray[0][$i] = substr($strDataIn, $i, 1);
            $temp[$i] = substr($strDataIn, $i, 1);
            $temp2[0][$i] = substr($strDataIn, $i, 1);
        }
       for ($i = 1; $i < $Length; $i++) 
       {
            for ($k = 0; $k < strLen($strDataIn); $k++) 
            {
                for ($j = 0; $j < sizeof($temp2[$i - 1]); $j++) 
                {
                    $PermArray[$i][($k * sizeof($temp2[$i - 1])) + $j] = $temp[$k] . $temp2[$i - 1][$j];
                    $temp2[$i][($k * sizeof($temp2[$i - 1])) + $j] = $temp[$k] . $temp2[$i - 1][$j];
                }
            }
        }
        $k = 0;
        for ($i = 0; $i < $Length; $i++) 
        {
            $k += sizeof($PermArray[$i]);
        }
        $PermutateCount = $k;
        return $PermArray;
    }
    
     $StartString = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
     $len = 4;
     $Return = Permutate($StartString, $len, $cnt);
     
     $i = $len -1;
     
     $cnt = sizeof($Return[$i]);
     
     print "Returned <b>$cnt</b> permutations.<br><hr>";
     
     //for ($i = 0; $i < $len; $i++) 
     //{
        for ($j = 0; $j < sizeof($Return[$i]); $j++) 
        {
            print $Return[$i][$j] . "<br>";
        }
        print "<br>";
     //}
 ?>

Re: combinatoric

Posted: Tue Aug 09, 2011 3:42 pm
by turbo535
Thank you very much... Now this script show only 4 charters, but not unique. I need only AABB, AABA not AAAA, AAAB.

Re: combinatoric

Posted: Tue Aug 09, 2011 6:04 pm
by McInfo
The characters in "AABB" are not unique either. Do you mean

Code: Select all

ABCD ABDC ACBD ACDB ADBC ADCB
BACD BADC BCAD BCDA BDAC BDCA
CABD CADB CBAD CBDA CDAB CDBA
DABC DACB DBAC DBCA DCAB DCBA

Re: combinatoric

Posted: Tue Aug 09, 2011 6:10 pm
by turbo535
correct.

Re: combinatoric

Posted: Tue Aug 09, 2011 6:23 pm
by McInfo
May I ask what you need this for? Finding all permutations gets computationally expensive very quickly. It might not be the ideal strategy for your problem.

Re: combinatoric

Posted: Wed Aug 10, 2011 10:00 am
by turbo535
With 4 charters it's easy, but with 8, 9 or 10 charters?

Re: combinatoric

Posted: Wed Aug 10, 2011 12:57 pm
by Dodon
Let's says you got the same piece of string which has 26 chars => "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

at length 4 you get 456976 results, running your script it takes a few seconds to load the page.
at length 8 you get 208827064576 results (26^8)
at length 9 you get 5429503678976 results (26^9)
at length 10 you get 141167095653376 results (26^10)

seeing those numbers the script would have to run for ages to come with a result.

Re: combinatoric

Posted: Wed Aug 10, 2011 1:50 pm
by turbo535
But I need it.

Re: combinatoric

Posted: Wed Aug 10, 2011 2:10 pm
by McInfo
Here is a table to emphasize the point. A 26-character set is assumed.
  • Length: Number of characters in each permutation
  • Seconds: Computation time to generate all permutations of the given length
  • Permutations: Number of unique ways to order the characters

Code: Select all

+--------+--------------+--------------------+
| Length |    Seconds   |    Permutations    |
+--------+--------------+--------------------+
|      1 |       0.0005 |                 26 |
|      2 |       0.01   |                650 |
|      3 |       0.2    |             15 600 |
|      4 |       3      |            358 800 |
|      5 |      80      |          7 893 600 |
|      6 |     xxx      |        165 765 600 |
|      7 |    xxxx      |      3 315 312 000 |
|      8 |   xxxxx      |     62 990 928 000 |
|      9 |  xxxxxx      |  1 133 836 704 000 |
|     10 | xxxxxxx      | 19 275 223 968 000 |
+--------+--------------+--------------------+
To put the number of seconds in perspective, here are some conversions.

Code: Select all

   300 seconds = 5 minutes
  3600 seconds = 1 hour
 86400 seconds = 1 day
604800 seconds = 1 week
Writing a function to generate all permutations of more than a few characters is an exercise in futility. That's not an accusation--I actually have written such a function.

Anyway, to find the pattern, start with what you know. For instance, you know how to write a loop to generate a list of the 26 letters of the alphabet. Once you succeed with that, add a loop within the loop to concatenate two letters. You don't want the two letters to be the same, so you need a way to remember what you have used already. Try employing a variable to store the character at the first position. If the second character matches the first, skip it.

When you add a third loop inside the second, you will need to remember what characters are in the previous two positions. If the third character matches either the first or second, skip it. Now or later, using individual variables becomes cumbersome. Arrays are better suited for handling multiple related values. An array key should determine the character position. An array value is the character at that position.

You may notice that in the course of adding, modifying, and deleting the characters in the array, it is only the last character that ever changes. Because of this, we can call the array a "stack". To move to the next character position, "push" a character onto the stack. To move back to a previous character position, "pop" a character off the stack.

All of the loops appear pretty much the same, like a hall of mirrors. However, within the deepest inner loop, something a little different happens. Instead of a loop like the others, there is a loop to join the characters of the stack together to form a string which comprises a single permutation.

When you understand the pattern, you can simplify the code by writing a recursive function instead of the many nested loops. Besides making the code more compact, recursion allows you to have an arbitrary number of nested loops, and thus an arbitrary length of the resulting strings.