PHPの文字列の順列

Question

長さが7より長い文字列の順列を見つけているときに、私のコードに問題があります。例えば、 'abcdefgh'のように。私は12語までの単語の順列を見つけなければならない。私のコードを見直し、最適化ができるかどうかを提案してください。

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

Answer 1

ソリューションのコアはすべてをチェックしないであるべきであるように思えます。たとえば、「地震」という言葉を与えた場合は、「qk」で始まるものについては辞書の単語がないことがすぐにわかるはずです。したがって、q k _ _ _ _ _ _ _ _ _という形式のすべての順列をチェックする必要はありません。このタイプのチェックは、多くの比較操作とルックアップ操作を節約します。この「qk」の例だけでは、それ以外の場合にチェックする必要があった362,880（9！）の置換が除外されます。

したがって、すべての順列を計算する代わりに、順列の1つに一致する場合は辞書から引き出して、生成している各順列が実際に可能な単語であることを確認します。