最近、サブセットアルゴリズムの質問に苦労しています。
char文字列からすべてのサブセットを取得するにはどうすればよいですか？
条件：各サブセットは、元の文字列のすべての異なる文字をカバーすることはできません。
たとえば、abbc、[a、b、c]->出力-> a、b、c、ab、abb、bbc、bb、bc
サブセット：{abc}、および{abbc}を削除する必要があります！
私の最初の考えは、元の文字列をa1b2c1に前処理してから再帰的に実行し、各再帰レイヤーが1つの異なる文字を処理することです。最後のレイヤーでは、ここのように、プロセスcが必要です。サブセットにcを入れるかどうかは、前のレイヤーから渡された情報によって異なります。
私のアイデアが良いかどうかわかりませんが、この質問について誰かがアイデアを持っていますか？
最悪のシナリオでは、すべての2 ^ nサブセットを処理する必要があるため、時間的に改善できるとは思いません。答えに対するあなたの考えは、そのようにかなり良いです。
次の再帰ステップに渡す必要がある唯一の情報は、これまですべての個別の文字を選択したかどうかです。これはたった1ビットで実行できます。次に例を示します。
値とカウントのペアをv [i]とc [i]として示します。nがそのようなペアの数を表すとします。再帰関数の状態は次のように定義できます。
F（i、b）=値> v [i]を含むすべてのサブセットを返します。b = 1、これらのサブセットにすべての個別のメンバーを含めるべきではない場合。F（n、b）は、上記の再帰に対する自明な解です。
あなたはF（0、1）を求めます
当然、考えられるすべてのケース、つまりサブセットに含まれるv [i]の数を検討するには、j = 0からc [i]まで反復する必要があります。j = 0またはb = 0の場合、次の帰納的集合はb = 0になります。それ以外の場合は、1になります。
これにより、求めるすべてのサブセットが生成されます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加