集合のすべてのサブセットを求めます(続き)

前の「集合を求めるすべてのサブセット」で与えられた2つの方法は、すべてのサブセットを求める問題を解決したが、辞書順に基づいてすべてのサブセットを出力できない欠陥も残っている.ここでは遡及法を用いて解き,辞書順にすべてのサブセットを出力することを保証した.大まかな考え方:
まず、選択したすべての要素の下付きラベルを記録するには、補助配列indexを使用します.補助配列indexについては、次の2つの条件を満たす必要があります.
(1)index[i+1]>index[i]すなわち、後の要素の下付き文字は前の要素の下付き文字より大きくなければならない
(2)index[i]-i<=m-n(サブセットのi+1番目の要素を表すm個の要素からn個の要素のサブセットを選択)
既存のセットset{a,b,c,d,e}がある場合、セットsetで3つの要素のすべてのサブセットを選択することを求める.大まかな流れは以下の通りです.
(1)最初の要素を選択すると、i=0、index[i]=0となり、以上の2つの条件を満たし、規模を拡大し、i=1、index[1]=index[0]+1=1となる.この方法で規模を拡大し続け、第1のグループ解:index[0]=0、index[1]=1、index[2]=2、i=2を得る
(2)index[2]上の2は3と4の両方が上記の条件を満たすように調整されているため,この解に基づいて次の解を計算すると,他の2組の解が得られる.
         index[0] = 0, index[1] = 1, index[2] = 3, i = 3
         index[0] = 0, index[1] = 1, index[2] = 4, i = 4
(3)index[2]=5の場合、第2の条件が満たされなくなるため、index[1]に遡及し、index[1]を2に調整し、index[0]から遡及するまで以上の手順で計算を継続し、すべてのサブセットが求められたことを示す.
具体的なコードは以下のように実現される.

#include <iostream>
using namespace std;

template<class T>
void Output(T set[], int index[], int k, int n)
{
    bool flag = false;
    cout << "{";

    for (int i = 0; i < n; i++)
    {
        if (flag)
        {
            cout << ", ";
        }
        cout << set[index[i] + k];
        flag = true;
    }
    cout << "}" << endl;

    return;
}

//   set[k:m]   n      
template<class T>
int SubSet(T set[], int k, int m, int n)  
{  
    int i = 0;
    int index[10]; //    ，         

    //      
    if (0 == n)
    {
        Output(set, index, k, n);
        return 0;
    }  
    index[i] = 0;  

    while (true)  
    {  
        if (index[i] - i <= m - k + 1 - n) //         
        {  
            if (i == n - 1) //       
            {  
                Output(set, index, k, n);  
                index[i]++;  
                continue;  
            } 
            i++; //        
            index[i] = index[i - 1] + 1;  
        }  
        else //    
        {  
            if (i == 0) //       
            {
                return 0;
            }
            index[--i]++;  
        }  
    }

    return 0;
}

//    set[k:m]     
template<class T>
int SubSet(T set[], int k, int m)
{
    for (int i = 0; i <= m - k + 1; i++)
    {
        SubSet(set, k, m, i);
    }

    return 0;
}

int main(int argc, char *argv[])
{
    char str[10];
    cout << "         :";  
    cin >> str;
    SubSet(str, 0, strlen(str) - 1);
    system("PAUSE");
    return EXIT_SUCCESS;
}