0

I have problem with my code while finding permutation of string for string with length greater than 7. For eg 'abcdefgh'. I have to find the permutation of word up to 12 length. Please review my code and suggest if any optimization can be done.

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 the result */
    return $permutations;
}

$arr = permute('abcdefghijkl');
nickb
  • 59,313
  • 13
  • 108
  • 143
ratna
  • 67
  • 1
  • 5
  • Can you estimate the *number* of permutations of a string of length `n`, and how fast that number grows? – Kerrek SB Nov 15 '11 at 01:27
  • What's wrong with it? Permutations run in O(n!) so it should take a long time to run for 12 length strings as 12! is a large number. – Jesus Ramos Nov 15 '11 at 01:27
  • Although there's a trick to generate the nth permutation in polynomial time but if you want all permutations you need to calculate all n! of them. – Jesus Ramos Nov 15 '11 at 01:29
  • my actual problem is to fetch all possible combination of this string from database for a Anagrammer game. I am tired.. can't find the right solution and algorithm for string with length 12 – ratna Nov 15 '11 at 01:33
  • @Jesus Ramos : I have list of words in database. If user submits string 'abcdefghijkl' then it should return all possible combination of words from database. What i did is , i find all permutation of words and searched in mysql database as where word in '%ab%','%cd%' etc. Please help!! – ratna Nov 15 '11 at 01:36
  • http://stackoverflow.com/questions/7187140/anagram-algorithm – cetver Nov 15 '11 at 01:43
  • 1
    I think you need to think about a different way to do this. It seems like you are going to have 1 billion "in statements" to your database? – Paul Nov 15 '11 at 01:46
  • Either you will have a large database where a sorted string (character sort) maps to a list of permutations or you have to generate them on the fly. One is heavy on the processing the other will add ALOT of data to your DB. pick your poison I guess. Permutations can't be computed any faster (sure you can shave off constants but the dominating n! factor remains). – Jesus Ramos Nov 15 '11 at 01:48
  • it would be better if there is any way to find permutation of words using query i tried like. for eg apple select * from table name where word like '%a%p%p%l%e'. but didn't work – ratna Nov 15 '11 at 02:28

1 Answers1

0

It seems like the core of the solution should lie in not checking everything. For example, if you give me the word "earthquakes", it should be immediately evident that there are no dictionary words for anything beginning with "qk", thus checking all permutations of the form q k _ _ _ _ _ _ _ _ _ is unnecessary. This type of check will save you a lot of comparison and lookup operations. This "qk" example alone would rule out 362,880 (9!) permutations that you would have needed to check otherwise.

So instead of calculating ALL the permutations, then pulling from the dictionary if it matches one of the permutations, I would make sure that each permutation you're generating is actually a possible word first.

Jon Newmuis
  • 25,722
  • 2
  • 45
  • 57