サブセット生成アルゴリズム

サブセット生成アルゴリズムは暴力法において非常に重要なアルゴリズムである.
タイトルの説明
集合を与えて、アルゴリズムを書いて、そのすべてのサブセットを得てください.ここで、この集合に重複する要素は存在しないと仮定する.
栗を挙げると、[1, 2, 3]の集合が与えられ、このようなサブセットに戻ります.

[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]

いちほうこうりょうほう
離散数学の知識によると、1つの長さnの集合のサブセットは2 n個あり、集合の要素は実は1つの長さnの2進数に対応することができることが分かる.この2進数のi番目のビットが1である、集合のi番目の要素をとることを示し、そうでない場合は取らないことを示す.
例えば、[1, 2, 3]は、3の長さの2進数に対応するもよい.111は[1, 2, 3]、011は[2, 3]を表す.
2進数000...00~111...11は、それぞれの数が1つのサブセットに対応する、まずこれらの数がそれぞれ異なり、次いでこれらの数の総数が2 nであるため、これらの数に対応するサブセットは、その集合の全サブセットにちょうど対応する.
以下に、この方法の簡単な実装を示します.

#include 
#include 
#include 
using namespace std;

/**
 *     .
 *     set      n,        n bool        ,    i    true,    set
 *     i   ,        .          000....00 (n 0)     ,      111...11
 *   (n 1)  ,              ,    set     .    ,             .
 *       ,  set [1, 2, 3],    001     3   , [3] set     .
 *      111  [1, 2, 3] set     .
 */

/**
 * @brief        
 * @param[in] set   
 * @param[in] mask    
 * @param[in] pos          pos    .
 * @param[in, out] subsets          .
 */
void findSubSets(vector<int>& set, bool mask[], int pos, vector<vector<int>>& subsets)
{
    if (pos == set.size()) { /*        */
        vector<int> subset;
        for (int i = 0; i < set.size(); i++) {
            if (mask[i]) subset.push_back(set[i]);
        }
        subsets.push_back(subset);
        return;
    }
    mask[pos] = true;
    findSubSets(set, mask, pos + 1, subsets);
    mask[pos] = false;
    findSubSets(set, mask, pos + 1, subsets);
}

/**
 * @brief   set     .
 * @param[in] set           
 * @return          
 */
vector<vector<int>> subSets(vector<int>& set)
{
    bool mask[1024];
    vector<vector<int>> subsets;  /*           */
    findSubSets(set, mask, 0, subsets);
    return subsets;
}

int main()
{
    vector<int> nums = { 1, 2, 3 };
    auto subsets = subSets(nums);
    for (auto &subset : subsets) {
        for (auto elem : subset) {
            cout << elem << " ";
        }
        cout << endl;
    }
    getchar();
}

インクリメンタルこうぞうほう
この方法は上のポテンシャル法より少し理解しにくいが、やり方もかなり面白い.

は、長さiのサブセットがあり、このサブセットがセットの前のk要素の組み合わせによって生成されたと仮定し、明らかにk <= iである.では、このサブセットを介して長さi+1のサブセットを生成するのか.

簡単で、当然、集合の後n-k個の要素を遍歴し、各要素をそのサブセットの後に追加すればよい.

は、集合前のk個の要素からなるすべてのサブセットがすでに存在し、長さが2 kであると仮定し、集合前のk+1個の要素からなるすべてのサブセットをどのように生成するか.

簡単に、集合のk+1番目の要素について、前のk個の要素からなるサブセットを追加することで、2 kのサブセットを生成することができる.追加しないことを選択する、2 kのサブセットを生成することができ、ちょうど前のk個の要素からなるサブセットである.
増分構造法はこの2点を結合する.
この方法の簡単な実現は以下の通りである.

#include 
#include 
#include 
using namespace std;

/**
 *      
 *                  .   ,         ,               
 *       .
 */

/**
 * @brief        subsetIdx + 1   
 * @param[in] set        
 * @param[in] setIdx           0~setIdx-1     setIdx             .
 * @param[in] subset      setIdx          subsetIdx   .
 * @param[in] subsetIdx      .
 * @param[in/out] subsets             
 * @return  
 */
void findSubsets(vector<int>& set, int setIdx, int* subset, int subsetIdx, vector<vector<int>>& subsets)
{
    /**
     *         subsetIdx,         setIdx       ,            
     * subsetIdx+1    ?
     */  
    for (int i = setIdx; i < set.size(); i++) {
        /*    subset     i          ,         i+1         ? */
        /*   set  i+1     subset subsetIdx       */
        subset[subsetIdx] = set[i];
        /*      ,   subsetIdx+1     subsets */
        subsets.push_back(vector<int>(subset, subset + subsetIdx + 1));
        /*      i   ,   subset    subsetIdx,    subsets   */
        /**
         *       ,           i+1        ,   subsetIdx+1   ,
         *                          .i+1          ,set 
         * 0~i          .
         * subsetIdx+1   subsetIdx         ,             .
         */
        findSubsets(set, i + 1, subset, subsetIdx + 1, subsets);
    }
}

/**
* @brief   set     .
* @param[in] set           
* @return          
*/
vector<vector<int>> subSets(vector<int>& set) {
    vector<vector<int>> subsets;
    int subset[1024];
    findSubsets(set, 0, subset, 0, subsets);
    return subsets;
}


int main()
{
    vector<int> nums = { 1, 2, 3 };
    auto subsets = subSets(nums);
    for (auto &subset : subsets) {
        for (auto elem : subset) {
            cout << elem << " ";
        }
        cout << endl;
    }
    getchar();
}