combinatoric

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
turbo535
Forum Newbie
Posts: 5
Joined: Tue Aug 09, 2011 7:09 am

combinatoric

Post 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.
Dodon
Forum Commoner
Posts: 64
Joined: Wed Aug 03, 2011 4:11 am
Location: Netherlands

Re: combinatoric

Post 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>";
     //}
 ?>
turbo535
Forum Newbie
Posts: 5
Joined: Tue Aug 09, 2011 7:09 am

Re: combinatoric

Post by turbo535 »

Thank you very much... Now this script show only 4 charters, but not unique. I need only AABB, AABA not AAAA, AAAB.
User avatar
McInfo
DevNet Resident
Posts: 1532
Joined: Wed Apr 01, 2009 1:31 pm

Re: combinatoric

Post 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
Last edited by McInfo on Tue Aug 09, 2011 6:15 pm, edited 2 times in total.
turbo535
Forum Newbie
Posts: 5
Joined: Tue Aug 09, 2011 7:09 am

Re: combinatoric

Post by turbo535 »

correct.
User avatar
McInfo
DevNet Resident
Posts: 1532
Joined: Wed Apr 01, 2009 1:31 pm

Re: combinatoric

Post 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.
turbo535
Forum Newbie
Posts: 5
Joined: Tue Aug 09, 2011 7:09 am

Re: combinatoric

Post by turbo535 »

With 4 charters it's easy, but with 8, 9 or 10 charters?
Dodon
Forum Commoner
Posts: 64
Joined: Wed Aug 03, 2011 4:11 am
Location: Netherlands

Re: combinatoric

Post 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.
turbo535
Forum Newbie
Posts: 5
Joined: Tue Aug 09, 2011 7:09 am

Re: combinatoric

Post by turbo535 »

But I need it.
User avatar
McInfo
DevNet Resident
Posts: 1532
Joined: Wed Apr 01, 2009 1:31 pm

Re: combinatoric

Post 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.
Post Reply