私は、文字セットを最大ワード数を含む順列にスクランブリングするための効率的なアルゴリズムを探しています。効率的なワードスクランブルアルゴリズム
例えば、{e、e、h、r、s、t}という文字のリストが与えられているとします。私は、最大数の単語を含むような方法でそれらを注文する必要があります。これらの文字を「theres」に注文すると、「the」、「there」、「her」、「here」、「ere」という単語が含まれています。この例では5単語が含まれているので、5というスコアを持つことができます。私は最高のスコア（最も多くの単語を含む）を持つような方法で手紙を注文したい。
純粋なアルゴリズムはすべての置換を試してみることです。私はこれがO（n！）だと信じているので、上記の6文字だけで720個の異なる置換が試されます（例にはeが2回あるためいくつかの重複を含みます）。より多くの手紙については、素朴な解決策はすぐに不可能になります。
このアルゴリズムは実際には最高のソリューションを生み出す必要はありませんが、妥当な時間内に良い解決策を見つけるはずです。私のアプリケーションでは、（Monte Carlo）を数百万個の順列で推測するだけでは問題はありません。
現在、Aho-Corasickアルゴリズムを使用して順列をスコア付けしています。それは、テキストの1回のパスで辞書内の各単語を検索するので、かなり効率的です。これはまた、すべての単語がtrieに格納されていることを意味しますが、別のアルゴリズムでも別のストレージが必要な場合は、それも問題ありません。私は実際の注文と検索の実行時間だけ、辞書の設定について心配していません。必要に応じて、Bloom Filterのようなファジー辞書を使用することもできます。
私のアプリケーションでは、指定された文字のリストは約100であり、辞書には100,000を超えるエントリが含まれています。辞書は決して変更されませんが、いくつかの異なる文字のリストを注文する必要があります。
私はpath finding algorithmを試してみることを検討しています。私は出発点としてリストからランダムな文字で始めることができると信じています。その後、残りの文字はそれぞれ「パス」を作成するために使用されます。私はこれがAho-Corasickの得点アルゴリズムとうまくいくと思っています。スコアは一度に1文字ずつ作成できるからです。私はまだパスの検索を試みたことはありません。多分それはいい考えではないでしょうか？どの経路発見アルゴリズムが最良かもしれないか分かりません。
もう1つのアルゴリズムは、ランダムな文字でも始まります。次に、辞書トライは、残りの文字を含む「リッチ」ブランチについて検索される。使用できない文字を含むディクショナリブランチは、削除されます。私はこれがどのように正確に機能するかについての詳細については少し曇っていますが、スコアリング順列を完全に排除することができます。
偉大な質問、よく尋ねられました！ – erickson
これは単語です。それはあなたの元の例題5の得点になります。 –
それはNPのようなものです。何か、笑。 –