再帰を使用して1つのセットのすべてのサブセットを求める

考えてみてください.普段1、2、3、4の4つの数をあげて、そのすべてのサブセットを書かせたら、あなたはどうしますか.ほとんどの人の考えは、まずサブセットに1つの要素しか含まれていないサブセットを書くことだと思います:1;2;3;4.次に、サブセットに2つの要素のサブセットが含まれていることを考慮します:1,2;1,3;1,4;2,3;2,4;3,4.次に、サブセットに3つの要素のサブセットが含まれます.1,2,3;1,2,4;1,3,4;2,3,4.最後は自分:1,2,3,4.もちろんもう一つの空集があることを忘れないでください.はい、そう考えることができれば、考えがはっきりしています.私たちが今書いているプログラムの考え方はこれと同じです.まず、探しているサブセットの要素の個数をループで制御し、関数の中でさっき私たちが手書きしたときの考え方を復元し始めます.実験を開始する前に、abcdのacdを出力したい場合は1011で表し、最終的に出力するときに各文字が1に対応するか0に対応するかを判断するテクニックを理解します.たとえば,{a,b,c,d,e}という集合の3つの要素を含むサブセットを検索します.我々は,まずa(すなわちaが1に対応する)を固定し,次に残りの{b,c,d,e}から2つを見つけることを目標とし,明らかにこの作業は我々以前と同じであるため,再帰関数を呼び出してこの問題を解決することができる.今、私たちはまずこの再帰関数が具体的にどのように書かれているかにかかわらず、まず考えを整理します.aを含むサブセットが完了したら、b(すなわちbは1)を固定し、aに対応する1を0に変更することを忘れないでください.そうしないと、aを出力します.次に{c,d,e}から2つの数を見つけなければならないことを明らかにします.bを完成して、c,d,eに対して同じ仕事をします.待って!3つの要素を含むサブセットを見つけ出すには、それぞれa,b,cを固定すればよいようですが、dやeでは3つも集められないでしょう.はい、だから私たちはa,b,cを固定するだけでいいです.この再帰関数をどう書くべきか、もう一つの疑問は、この再帰関数がいつ終わるのかということだ.この関数を最後に再帰するにはいくつかの要素が残っていると思いますか?答えは1つ!したがって,固定されていない残りの要素のうち1つを見つけるには再帰関数を呼び出す必要はなく,forループを直接用いて残りの数の中から順次取り出し,さっきの01メソッドを用いてabcdeのうちどれを出力するかを決定する.完全な考え方はこうです.次に、上記のアイデアをコード形式で書きます.

//         27:      ，         1 1      
//a:bitset<27>     ，    1 0. chr:  a->z    27 char   
void CSet(int index, int n,int size) {//index:     n:           n  size:  size   
    if (n == 0)//  
        cout << endl;
    else if (n == 1) {//        1 
        for (int i = index; i <= size; i++) {
            a[i] = 1;
            for (int i = 1; i <= size; i++)
                if (a[i])
                    cout << chr[i]<<" ";
            cout << endl;
            a[i] = 0;
        }
    }
    else {//         2        
        for (int i = index; i <= size - n+1; i++) {
            a[i] = 1;
            CSet(i + 1, n - 1, size);
            a[i] = 0;
        }
    }
}

26文字の集合のすべてのサブセットを見つけるには、次のように書くことができます.

for (int i = 0; i <= 26; i++) {
        cout << "         " << i << "    :" << endl;
        CSet(1, i, n);
    }

上の煩雑な方法を紹介した後、もう一つの奇技を紹介します.上の本質は、出力が1,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,ここにはコードが貼られていません.