3

特定のセットのすべてのサブセットを見つけるための再帰的バックトラッキング アルゴリズムを作成しました。

void backtracke(int* a, int k, int n)
{
    if (k == n)
    {
        for(int i = 1; i <=k; ++i)
        {
            if (a[i] == true)
            {
                std::cout << i << " ";
            }
        }
        std::cout << std::endl;
        return;
    }
    bool c[2];
    c[0] = false;
    c[1] = true;
    ++k;
    for(int i = 0; i < 2; ++i)
    {       
        a[k] = c[i];
        backtracke(a, k, n);
        a[k] = INT_MAX;
    }
}

今度は同じアルゴリズムを反復形式で作成する必要がありますが、どうすればよいでしょうか?

4

4 に答える 4

13

バイナリ カウンター アプローチを使用できます。長さ n の一意のバイナリ文字列は、n 個の要素のセットの一意のサブセットを表します。0 で始まり 2^n-1 で終わる場合、すべての可能なサブセットをカバーします。カウンタは、反復的な方法で簡単に実装できます。

Java のコード:

  public static void printAllSubsets(int[] arr) {
    byte[] counter = new byte[arr.length];

    while (true) {
      // Print combination
      for (int i = 0; i < counter.length; i++) {
        if (counter[i] != 0)
          System.out.print(arr[i] + " ");
      }
      System.out.println();

      // Increment counter
      int i = 0;
      while (i < counter.length && counter[i] == 1)
        counter[i++] = 0;
      if (i == counter.length)
        break;
      counter[i] = 1;
    }
  }

Java では BitSet を使用できるため、コードが非常に短くなりますが、プロセスをわかりやすくするためにバイト配列を使用したことに注意してください。

于 2014-03-09T08:59:04.630 に答える
8

この問題の反復アルゴリズムを作成するには、いくつかの方法があります。最も一般的に提案されるのは、次のことです。

  • カウント (つまり、単純な for ループ) from 0to to2numberOfElements - 1

  • 上でバイナリでカウントするために使用された変数を見ると、各位置の桁は、セット内の対応するインデックスの要素をこのサブセットに含める必要があるかどうかを示すフラグと考えることができます。出力に対応する要素を含めて、各ビットを単純にループします (剰余を 2 で割ってから 2 で割ります)。

例：

入力: {1,2,3,4,5}.

でカウントを開始します0。これは00000バイナリであり、フラグが設定されていないことを意味するため、要素は含まれません (空のサブセットが必要ない場合、これは明らかにスキップされます) - output {}。

次に1 = 00001、最後の要素のみが含まれることを示します - 出力{5}。

次に2 = 00010、最後から 2 番目の要素のみが含まれることを示します - 出力{4}。

次に3 = 00011、最後の 2 つの要素が含まれることを示します - 出力{4,5}。

まで31 = 11111、すべての要素が含まれることを示します - output {1,2,3,4,5}。

* 実際にはコード的には、最初の 2 による剰余が 0 番目の要素、2 番目の剰余、1 番目の要素などのフラグに対応することを考慮すると、これを頭に出力{1}する方が簡単です。00001上記は、説明のために単純化されています。

より一般的には、次のように再帰アルゴリズムを反復アルゴリズムに変更できます。

  • 関数内の任意の 2 つの再帰呼び出しの間のコードで構成される各部分で、部分 (switch-statement と考えてください) で構成されるループを作成します。

  • 各要素が関数内の必要な各ローカル変数を含むスタックを作成し、どの部分で忙しいかを示します

  • ループはスタックから要素をポップし、コードの適切なセクションを実行します

  • 各再帰呼び出しは、最初に独自の状態をスタックに追加し、次に呼び出された状態を追加することで置き換えられます

  • return適切なbreakステートメントに置き換えます

于 2014-03-09T09:19:52.597 に答える
4

Georgeのアルゴリズムの小さな Python 実装。おそらくそれは誰かを助けるでしょう。

def subsets(S):
    l = len(S)
    for x in range(2**l):
        yield {s for i,s in enumerate(S) if ((x / 2**i) % 2) // 1 == 1}
于 2015-01-25T10:47:57.627 に答える
1

基本的にあなたが望むのは P(S) = S_0 U S_1 U ... U S_n ここで、S_i は S から i 個の要素を取得することによって含まれるすべてのセットのセットです。つまり、S= {a、b、c} の場合、S_0 = {{}}、S_1 = {{a}、{b}、{c}}、S_2 = {{a、b}、{a、c}、{b、c}}、S_3 = {a、b 、c}。

これまでのアルゴリズムは

set P(set S) {
    PS = {}
    for i in [0..|S|]
        PS = PS U Combination(S, i)
    return PS
}

|S_i| = nCi ここで |S| = n. 基本的に、nCi 回ループすることはわかっています。この情報を使用して、後でアルゴリズムを最適化できます。サイズ i の組み合わせを生成するために、私が提示するアルゴリズムは次のとおりです。

S = {a, b, c} とすると、0 を a に、1 を b に、2 を c にマッピングできます。これらの順列は (i=2 の場合) 0-0、0-1、0-2、1-0、1-1、1-2、2-0、2-1、2-2 です。シーケンスが組み合わせであるかどうかを確認するには、数字がすべて一意であるかどうかを確認し、数字を並べ替えるとシーケンスが他の場所に表示されないことを確認します。これにより、上記のシーケンスが 0-1、0-2、および 1-2 だけにフィルター処理されます。これらは後で {a,b}、{a,c}、{b,c} にマップされます。上記の長いシーケンスを生成する方法は、このアルゴリズムに従うことができます

 set Combination(set S, integer l) {
     CS = {}
     for x in [0..2^l] {
         n = {}
         for i in [0..l] {
             n = n U {floor(x / |S|^i) mod |S|} // get the i-th digit in x base |S|
         }
         CS = CS U {S[n]}
     }
     return filter(CS) // filtering described above
 }
于 2014-03-09T09:14:11.970 に答える