Need Permutation Algorithm
Posted: Mon Jul 05, 2010 6:38 pm
I am trying to create code that returns an array of all permutations of a letter combination in a string.
For example, if I have the string 'ABC', it would return the following array:
{ 'ABC','ACB','BCA','BAC','CAB','CBA' }
I found some PHP code that does this, but I don't understand the FOREACH loop, even though I have a book on PHP. I'm trying to convert the below code to Xbase++. Does anyone have any ideas?
aArray := Permute('ABC')
This needs to be a fast algorithm because I will be using it for 7 character strings which produce a factorial (Array Size) of 5040.
For example, if I have the string 'ABC', it would return the following array:
{ 'ABC','ACB','BCA','BAC','CAB','CBA' }
I found some PHP code that does this, but I don't understand the FOREACH loop, even though I have a book on PHP. I'm trying to convert the below code to Xbase++. Does anyone have any ideas?
aArray := Permute('ABC')
This needs to be a fast algorithm because I will be using it for 7 character strings which produce a factorial (Array Size) of 5040.
Code: Select all
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;
}