セットからすべての可能な順序付きサブセットを生成

Question

私は、ビットツイディングを組み込んだセットからすべての可能なサブセットを生成する方法を知っています。例えば、

//Get if nth position's bit is set 
bool IsBitSet(int num, int bit) 
{ 
    return 1 == ((num >> bit) & 1); 
} 

int subsetMaxIterCount = pow(2, someList.size()); 
for (int i = 0; i < subsetMaxIterCount; i++) { 
    vector<A> subset; 
     for (size_t i = 0; i < jobList.size(); i++) 
     { 
      if (IsBitSet(jobSubsetIdx, i)) { 
       //Add to subset here 
      } 
     } 

     //Here we have a subset for some i 
    } 

ただし、これは発注を考慮していません。例えば

、私は設定していた場合は{1、2、3}、上記のアルゴリズムは、サブセット生成：

{}、{1}、{2}、{3}、{1、 2}、{1,3}、{2,3}、{1,2,3}

Iは実際に必要なものこの

{}、{1}、{2}、{3 }、{1,2}、{1,3}、{2,3}、{1,2,3}、{2,1}、{2,1,3}、{2,3,1}、 {3,1}、{3,2}、{3,1,2}、{3,2,1}

上記の一覧が網羅的であるかどうかは不明です。このようなものを生成する効果的なアルゴリズムは何ですか？ （途中で順列を持つすべての可能な部分集合ですか？）

Answer 1

ビットtwiddlingを使用して部分集合を生成する方法は、すべての部分集合がその中でソートされますe.g. {1, 2, 3}, {2, 3}, {1, 3}。あなたはまたnext_permutation

vector<vector<int>> mySubsetGenerator(vector<vector<int>>& subsets) { 
    vector<vector<int>> extendedSubset; 
    for(int i = 0; i < subsets.size(); ++i) { 
     do { 
      extendedSubset.push_back(subsets[i]); 
     } while(next_permutation(subsets[i].begin(), subsets[i].end())); 
    } 
    return extendedSubset; 
} 

を使用して、各サブセットのための順列を生成することができ、あなたは、配列の1つの以上の要素を取ることによって、すべての可能な順列を生成するために、バックトラックのみ使用することができます。