String permutation in PHP

Some of the problems at Project Euler deals with string permutations. “What’s that?” you say?

“Permutation is the rearrangement of objects or symbols into distinguishable sequences.” (wikipedia.org)

Let’s say we have the word “tone” and we would like to produce every permutation of it:

“tone”
“otne”
“onte”
“onet”

and so forth…

Since I solve some of the Project Euler problems using PHP I have written a recursive function that generates permutations of strings and it looks a little something like this: (sorry about the way the code looks, but I couldn’t make wordpress make it look any better)

function permute($str) {
/* If we only have a single character, return it */
if (strlen($str) < 2) { return array($str); } /* Initialize the return value */ $permutations = array(); /* Copy the string except for the first character */ $tail = substr($str, 1); /* Loop through the permutations of the substring created above */ foreach (permute($tail) as $permutation) { /* Get the length of the current permutation */ $length = strlen($permutation); /* Loop through the permutation and insert the first character of the original string between the two parts and store it in the result array */ for ($i = 0; $i <= $length; $i++) { $permutations[] = substr($permutation, 0, $i) . $str[0] . substr($permutation, $i); } } /* Return the result */ return $permutations; } [/sourcecode] If you want to produce every permutation of a string just pass it into the function and you will get an array back containing all the permutations. [sourcecode language="php"] $str = "tone"; $permutations = permute($str); [/sourcecode] If a character appears more than once in the string the array you get back will have duplicates. To make it unique just do: [sourcecode language="php"] $str = "toneo"; $permutations = array_unique(permute($str)); [/sourcecode] Be aware that this is a memory-hungry function if the string you want to work with is long.

Advertisements
This entry was posted in PHP and tagged , , , . Bookmark the permalink.

22 Responses to String permutation in PHP

  1. Pavan says:

    This works beautifully.
    I have one question, say if I had a 5 letter word but wanted to output 3 letter permutations of the word, how would I go about it?

  2. christer says:

    @Pavan: I’m not sure what you want to do… If the word is “would” … which three letters would you like to use for the permutation?

  3. Rahul says:

    this is nice n handy. thanks! could you also please suggest, if you’re aware of some simple books/resources which deal with such algos and their practical (or theoretical) applications like in ur case the Euler project?

  4. Justin says:

    @christer

    Pavan never came back to explain himself, I guess.

    I know what he’s wanting, because I’m looking for it myself.

    ABCDEF

    Has more permutations if you chop letters.

    ABCDE
    ABCDF

    BCDEF
    ABCD

    DEF

    This is useful if you feed it some characters such as “HISSSE” and you want it to find:

    HIS
    SIS
    HISS

    HISSES

  5. Lucas says:

    Man!!! You’re a genius, for sure!!!

    Thanks a lot. Simple and perfect code. I need this thing badly.

    I owe you.

  6. Repox says:

    Nice work – and its easy to read and understand your function :)

  7. Tom says:

    Nice one, this script is also good for finding unique website or usernames etc. Which is what I used it for :]

  8. rajesh says:

    how to find permutation of no. of strings stored in an array…php

  9. turist says:

    How to permute
    (abcdefghijklmnopqrstuxyz)
    but using only 3 letters.

    aab
    aac
    aad
    aaf
    .
    .
    .
    zaa
    zab
    zac
    .
    .
    .
    zzz

  10. turist says:

    Sorry mean 3 places.

  11. Bruce says:

    To determine the permutations of size length_perm that can be taken from a set of size length_string, try this:

    <?php
    $str="abcd";
    $length_perm = 3; //The size (length) of the desired permutation, say 3 letters
    $permutations = array_unique(permute($str));

    //Paste the function code from above

    //This will display all of the four letter permutations of "abcd"
    foreach($permutations as $word) {
    echo $word;
    echo "”;
    }

    //This will display all of the three letter permutations of “abcd”
    foreach($permutations as $word) {
    $permutations_3[] = substr($word,0,$length_perm);
    }
    $permutations_3u = array_unique($permutations_3);
    foreach($permutations_3u as $word) {
    echo $word;
    echo “” ;
    }

    //Seems to work – Count permutations and check against formula at: http://mathforum.org/dr.math/faq/faq.comb.perm.html
    ?>

  12. samyu says:

    can u tell me how to run this program

  13. Rahul Kadukar says:

    This is brilliant, recursion FTW, thanks a lot dude you rock :)

  14. I have a problem in producing “partial-conditional” permutation. Suppose there is an array as the basis:
    $arrBasis = array(“A”,”B”,”C”,”D”,”E”,”F”,”G”);
    And the sample pattern must be produced:
    A C B
    A D B
    A E B
    A F B
    A G B
    B C A
    B D A
    B E A
    ..and so forth.
    Is there any chance of using this code?
    Thank you.

  15. pinkynrg says:

    Does it stop working for words containing more than 8 letters? or is just me?

  16. Dzaky says:

    Bro.. can you help me to modify its input and output for me?
    i have input as array,
    Array ([0] => A [1] => B [2] => C)
    then i need output as new array,
    Array (
    [0] => Array ( [0] => A [1] => B [2] => C)
    [1] => Array ( [0] => A [1] => C [2] => B)
    .
    .
    [5] => Array ( [0] => C [1] => B [2] => A)
    )

    thanks ^^

  17. H. says:

    clearn code. good job.

  18. dcc0 says:

    In lexicographical order
    $a = array(1,2,3,4,5);
    $b = array_reverse($a);
    print_r($a);
    echo ‘
    ‘;

    while ($a != $b)
    {
    foreach(array_reverse($a, true) as $k => $v)
    {
    if ($v $val)
    {
    if ($val > $v) break;
    }

    $ch=$a[$k];
    $a[$k]=$a[$ka];
    $a[$ka]=$ch;

    $c = array_slice($a, 0, $k + 1);
    print_r($a=array_merge($c, array_reverse(array_slice($a, $k + 1))));

    echo ‘
    ‘;
    break;
    }
    }
    }

  19. dcc0 says:

    First if $v < $a[$k + 1])

  20. David says:

    How do I get 3 array tables from the permutation of $ip= array(
    58, 50, 42, 34, 26, 18, 10, 2,
    60, 52, 44, 36, 28, 20, 12, 4,
    62, 54, 46, 38, 30, 22, 14, 6,
    64, 56, 48, 40, 32, 24, 16, 8,
    57, 49, 41, 33, 25, 17, 9, 1,
    59, 51, 43, 35, 27, 19, 11, 3,
    61, 53, 45, 37, 29, 21, 13, 5,
    63, 55, 47, 39, 31, 23, 15, 7
    );
    in php. I only need the first three permutations of the array.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s