CODEWITHSUNDEEP
phpalgorithmanagram
Fredy
Fredy

Reputation: 2910

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

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?

Upvotes: 0

Views: 740

Answers (1)

Niet the Dark Absol
Niet the Dark Absol

Reputation: 324750

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 ;)

Upvotes: 3

Related Questions