How do I create a permutation of a string (10 characters long or more)?

Question

I got a task that makes me a little crazy, there is the section dealing with word permutations, after I browsing the internet I found a function to do permutations, as shown below:

function permute($str) {
    if (strlen($str) < 2) {
        return array($str);
    }
    $permutations = array();
    $tail = substr($str, 1);
    foreach (permute($tail) as $permutation) {
        $length = strlen($permutation);
        for ($i = 0; $i <= $length; $i++) {
            $permutations[] = substr($permutation, 0, $i) . $str[0] . substr($permutation, $i);
        }
    }

    return $permutations;
}

this to show the result:

print_r(array_unique(permute("abcdefghi"))); // found 362880
print_r(array_unique(permute("abcdefghij"))); // error

The problem is, this function is only able to perform all the permutations of 9 characters (approximately 362880 combinations, with a long time and make the browser not responding for tinytime). When trying to perform a permutation of up to 10 characters, an error message will appear:

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 35 bytes)

Do you have a solution or another way to do permutations with a length of 10 characters or more?

You're trying to do a simple random string generator? Because if yes, I have created one so I can send it to you... — Frederick Marcoux, Feb 11 '12 at 05:14
possible duplicate of [Permutation for string in php](http://stackoverflow.com/questions/8130411/permutation-for-string-in-php) — nickb, Feb 11 '12 at 05:16
In round numbers, you're trying to make an array of 4 million strings of 10 characters each. That's 40 megabytes plus overhead. The error message says there's a limit around 130 megabytes. So with overhead it sounds plausible that the output you want is just too big. Compute something different (generate the permutations one at a time instead of all at once?) or increase your limit. — Darius Bacon, Feb 11 '12 at 05:20
possible duplicate of [How to generate all permutations of a string in PHP?](http://stackoverflow.com/questions/2617055/how-to-generate-all-permutations-of-a-string-in-php) — Avinash, Feb 11 '12 at 05:56
#Frederick: Why not, please send me. Thank you,. #nickb: Its same.. :) #Darius: Thanks to information.. Its helpful.. #Avinash: Its another way, its helpful.. Thanks — Fredy, Feb 11 '12 at 06:24

score 3 · Accepted Answer · answered Feb 11 '12 at 05:21

The number of permutations of a string of length N is N!

So if you're just looking for the number of permutations, this will do:

function factorial($n) {
    if( $n == 0) return 1;
    if( $n < 3) return $n;
    return $n*factorial($n-1);
}
function permute($str) {
    return factorial(strlen($str));
}

If, however, you are trying to get a random one of those permutations, try this:

function permute($str) {
    $l = strlen($str);
    $a = str_split($str);
    $ret = "";
    while($l > 0) {
        $i = rand(0,$l-1);
        $ret .= $a[$i];
        array_splice($a,$i,1);
        $l--;
    }
    return $ret;
}

If you are trying to brute-force all N! permutations, try:

ini_set("memory_limit",-1);
set_time_limit(0);
// your brute-force code here

If none of these answer your question, please clarify ;)

"The number of permutations of a string of length `N` is `N!`" should've mentioned, this only applies if all the characters of the string are distinct. It's a bit more complicated if there's duplicates. — Niet the Dark Absol, Feb 11 '12 at 05:36

How do I create a permutation of a string (10 characters long or more)?

1 Answers1