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.

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?

You would just say $final = substr($permutation, 0, 3);

@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?

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?

@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

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

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

I owe you.

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

Nice algo.

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

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

How to permute

(abcdefghijklmnopqrstuxyz)

but using only 3 letters.

aab

aac

aad

aaf

.

.

.

zaa

zab

zac

.

.

.

zzz

Sorry mean 3 places.

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

?>

can u tell me how to run this program

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

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.

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

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 ^^

clearn code. good job.

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;

}

}

}

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

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.