アナグラム：
アナグラムは一種の言葉遊びであり、元の文字をすべて 1 回だけ使用して、単語またはフレーズの文字を並べ替えて新しい単語またはフレーズを作成した結果です。
部分和問題:
問題は次のとおりです。整数のセットが与えられた場合、合計がゼロである空でないサブセットはありますか?
たとえば、セット { −7, −3, −2, 5, 8} が与えられた場合、サブセット { −3, −2, 5} の合計はゼロになるため、答えはイエスです。問題は NP 完全です。
n 個の単語からなる辞書があるとします。ここで、アナグラム生成の問題は、入力のすべての文字を使い果たす辞書 (n 個の単語) 内の単語のセットを見つけることとして述べることができます。部分和問題のようなものになりませんか。
私が間違っている？
2 つの問題は似ていますが、同形ではありません。
アナグラムの発見 (多項式の回数を超えない) を解くことで部分和の問題が解決されることを証明できれば、それはコンピューター サイエンスの革命となるでしょう (P=NP を証明することになります)。
明らかにアナグラムを見つけることは多項式時間の問題です:
2 つのレコードが互いのアナグラムであるかどうかのチェックは、文字を並べ替えて結果の文字列を比較するのと同じくらい簡単です (つまりC*s*log(s)、sレコード内の文字の数)。-ディクショナリn内nのレコード数。したがって、明らかに実行時間 ~C*s*log(s)*nは、入力サイズの多項式 (入力レコードと辞書を組み合わせたもの) によって制限されます。
編集：
上記のすべては、アナグラム検出問題が、可能な完全なフレーズの辞書で入力フレーズのアナグラムを見つけることとして定義されている場合にのみ有効です。
上記の元の質問で問題を見つけるアナグラムの文言...
n 個の単語からなる辞書があるとします。ここで、アナグラム生成の問題は、入力のすべての文字を使い果たす辞書 (n 個の単語) 内の単語のセットを見つけることとして述べることができます。
...何か違うことを暗示しているようです-たとえば、辞書内の複数のエントリのある種の構成も、入力の可能なアナグラムの有効な選択である可能性があります。
ただし、これはすぐに問題があり不明確に思われます。なぜなら、(1) 通常、フレーズは単なるランダムな単語のシーケンスではなく (フレーズ全体として意味があるはずです)、(2) 通常、フレーズ内の単語には記号でもある区切り文字が必要なので、そうではないからです。ディクショナリ内の個別のエントリを許可するために入力にセパレータ (空白文字) が必要な場合、およびセパレータが単一のディクショナリ エントリで許可されている場合は、クリアします。
したがって、上記の最初の回答では、問題の定義を明確で「アナグラムの発見」として意味のある唯一の方法として解釈することにより、「セマンティック カミソリ」を適用しました。
しかし、著者の定義を次のように解釈することもできます。
n 文字シーケンスの辞書 (別個の辞書エントリに同じシーケンスが含まれる場合があります) と 1 つのターゲット文字シーケンスが与えられた場合 - 一緒に連結された場合にターゲット文字シーケンスの正確な再配置となる辞書エントリのサブセットを検索するか、そのようなサブセットが存在しないと判断します.
^^^- この問題はもはや「アナグラムを見つける問題」として完全に意味を成すものではありませんが、それでも興味深いものです。これは、私が上で考えたものとは非常に異なる問題です。
もう 1 つ不明な点があります。それは、アルファベットの柔軟性です。具体的には、問題の定義では、辞書と文字のターゲット シーケンスを指定するときに、文字セットが固定されているか、問題の新しいソリューションごとに再定義できるかどうかも指定する必要があります。これは重要です。機能と複雑さはそれに依存します。
各ソリューションのアルファベット (使用可能な文字数) を個別に定義する機能を備えたこの問題の変形は、実際には部分集合問題と同等です。これで NP 完全になります。
私たちの問題が、次のように定義された部分和問題の自然数バリアントと同等であることを証明できます。
自然数のコレクション (マルチセット) (繰り返し数を許可) とターゲット自然数が与えられた場合 - 合計がターゲット数に正確になるサブコレクションを見つけるか、そのようなサブコレクションが存在しないと判断します。
ある問題の入力を別の問題の入力に、またはその逆に変換するには、ほぼ直線的なステップ数で十分であることを理解するのは難しくありません。したがって、1 つの問題の解決策は、別の問題の正確な 1 つの解決策とほぼ線形のオーバーヘッドに変換されます。
この部分和の正のみの変種は、著者によって与えられたゼロ和部分和の変種と同等です (例えば、部分和のウィキペディアの記事を参照してください)。
私はあなたが間違っていると思います。
アナグラムの生成は、サブセットの合計よりも単純でなければなりません。なぜなら、それを解決するための自明な O(n) アルゴリズムを考案できるからです (定義どおり)。
initialize the list of anagrams to an empty list
iterate the dictionary word by word
if all the input letters are used in the ith word
add the word to the list of anagrams
return the list of anagrams
また、アナグラムは、入力単語の順列(つまり、再配置) である有効な単語で構成されますが、サブセットには順序の概念がありません。実際には、入力セット (したがってサブセット)よりも少ない要素が含まれる場合がありますが、アナグラムは常に入力単語と同じ長さでなければなりません。
単一の文字セットが与えられても、アナグラムのセットは関係なく同一のままであるため、NP-Complete ではありません。
入力 L の文字を一連のアナグラム A に変換する単一のマッピングが常に存在するため、f の任意の実行について f(L) = A と言えます。私が正しく理解していれば、これが関数を決定論的にすると信じています。Set の順序は無関係であるため、順序が異なるソリューションを非決定論的に考えると無効です。ディクショナリ内のすべてのエントリは一意であり、決定論的に順序付けできるため、無効でもあります。