フレーズアナグラムの効率的なアルゴリズム

Question

文字列を与えられたフレーズアナグラムを効率的に生成する方法はありますか？

私は

を解決しようとしている問題は、あなたがn個言葉で単語リストを持っていると仮定します。入力文字列、例えば "peanutbutter"が与えられると、すべてのフレーズアナグラムが生成されます。いくつかの候補があります：などエンドウ豆ナッツバター、Aしかしテン噴火、

私のソリューション

私は与えられた単語リスト内のすべての単語が含まれてトライを持っています。与えられた入力文字列を、私はすべての順列を計算します。各順列について、その特定の置換された文字列を単語に分割することができるかどうかを判断するために、再帰的な解決策（thisのようなもの）を持っています。たとえば、ピーナッツバターの順列の1つが「abuttenerupt」だった場合、私はこのメソッドを使って「10個のエラプト」に分解しました。私は文字列が有効な単語かどうかを判断するためにトライを使用します。

私の問題は、私はすべての順列を計算するので、私の解決策はがっかり大きい10文字より長いフレーズのために非常に遅い実行されることである吸う何

。これを別のやり方で行う方法があるかどうかを知りたい。 https://wordsmith.org/anagram/のようなウェブサイトは1秒未満で仕事をすることができます。私は彼らのやり方を知りたいと思っています。

Answer 1

パーミュテーションを生成し、それを単語に分解する2段階ソリューションの代わりに、再帰的にパーミュテーションを生成するときに有効な単語をチェックすることでスピードアップできます。あなたの現在の部分的に完全な順列が有効な単語に対応していない場合は、そこで停止し、それ以上は再帰しないでください。これは、無駄な順列を生成する時間を無駄にしないことを意味します。たとえば、 "tt"を生成する場合、 "peanubuter"を並べ替える必要はなく、ttで始まる英語の単語がないため、すべての順列を "tt"に追加する必要はありません。

基本的な再帰的置換の生成を行い、生成した現在の部分的な単語を追跡しているとします。有効な単語であれば、スペースを出力して新しい単語を開始し、残りの文字を再帰的に並べ替えることができます。現在の部分的な単語に残りの文字をそれぞれ追加することもできます。有効な部分的な単語（つまり、それらの文字から始まる単語）が得られた場合にのみ再帰します。このような

何か（擬似コード）：

void generateAnagrams(String partialAnagram, String currentWord, String remainingChars) 
{ 
     // at each point, you can either output a space, or each of the remaining chars: 

     // if the current word is a complete valid word, you can output a space 
     if(isValidWord(currentWord)) 
     { 
      // if there are no more remaining chars, output the anagram: 
      if(remainingChars.length == 0) 
      { 
       outputAnagram(partialAnagram); 
      } 
      else 
      { 
       // output a space and start a new word 
       generateAnagrams(partialAnagram + " ", "", remainingChars); 
      } 
     } 

     // for each of the chars in remainingChars, check if it can be 
     // added to currentWord, to produce a valid partial word (i.e. 
     // there is at least 1 word starting with these characters) 
     for(i = 0 to remainingChars.length - 1) 
     { 
      char c = remainingChars[i]; 
      if(isValidPartialWord(currentWord + c) 
      { 
       generateAnagrams(partialAnagram + c, currentWord + c, 
        remainingChars.remove(i)); 
      } 
     } 
} 

あなたが電流に対応トライでのノードを通過させることによって、さらに、このアルゴリズムを最適化することができ、この

よう

generateAnagrams("", "", "peanutbutter"); 

それを呼び出すことができ部分的に完成した単語だけでなく、currentWordを文字列として渡します。これにより、あなたのisValidPartialWordのチェックがさらに速くなります。

isValidWordのチェックを変更することで、単語が前の単語出力と比較して昇順（より大きいまたは等しい）のアルファベット順になっている場合にのみtrueを返すように設定することができます。同じ単語の2つが出力されるケースをキャッチするために、最後に偽のための別のチェックが必要な場合もあります。

Answer 2

あなたの問題は、2つのサブ問題に分解することができます：最初のサブ問題で見つかった単語のすべての順列を検索し、入力文字列

のすべての文字を使用した単語の

1. 検索の組み合わせ

サブプログラム＃2は基本的なアルゴリズムであり、ほとんどのプログラミング言語で既存の標準実装を見つけることができます。サブ問題＃1に焦点を当てましょう

最初に入力文字列を「文字プール」に変換します。文字プールを配列ocとして実装できます。ここではoc[c] =文字cの出現回数です。

result = empty; 

function findAnagram(pool) 
    if (pool empty) then print result; 
    for (word in dictionary) { 
    if (word fit in charpool) { 
     result = result + word; 
     update pool to exclude characters in word; 
     findAnagram(pool); 

     // as with any backtracking algorithm, we have to restore global states 
     restore pool; 
     restore result; 
    } 
    } 
} 

注：

はその後、我々は、この擬似コードのようにcharpoolに収まる単語を見つけるために、バックトラッキングアルゴリズムを使用して、我々は値によってcharpoolを渡す場合、我々はそれを復元する必要はありません。しかし、それはかなり大きいので、私は参考にして渡すことを好む。

今、私たちは、冗長な結果を削除し、いくつかの最適化を適用します。

• は、Aが辞書にBの前に来ると仮定します。最初の単語をBとすると、次のステップで単語Aを考慮する必要はありません。その結果（Aをとると）は、Aが最初の単語として選択された場合に既に存在するためです。

• 文字セットが十分に小さい場合（< 64文字が最適）、ビットマスクを使用してプールに収まらない単語をすばやくフィルタリングできます。何度もそれが起こっても、文字は単語の中にあるビットマスクです。

更新の擬似コードは、これらの最適化を反映するために：http://ideone.com/vf7Rpl：文字セットは、小文字のみ '' .. 'Z' を含む副問題＃1の

function findAnagram(charpool, minDictionaryIndex) 
    pool_bitmask <- bitmask(charpool); 
    if (pool empty) then print result; 
    for (word in dictionary AND word's index >= minDictionaryIndex) { 
    // bitmask of every words in the dictionary should be pre-calculated 
    word_bitmask <- bitmask(word) 
    if (word_bitmask contains bit(s) that is not in pool_bitmask) 
     then skip this for iteration 
    if (word fit in charpool) { 
     result = result + word; 
     update charpool to exclude characters in word; 
     findAnagram(charpool, word's index); 

     // as with any backtracking algorithm, we have to restore global states 
     restore pool; 
     restore result; 
    } 
    } 
} 

私のC++実装を。