从集合中生成所有可能的有序子集

问题描述：

我知道如何从一个包含位混合的集合中生成所有可能的子集。例如，从集合中生成所有可能的有序子集

//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}

我需要在现实中是这样

{}，{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}

不确定以上列表是否详尽。生成这样的东西的有效算法是什么？（这是所有可能的子集与顺序排列的方式？）

是的。生成子集，然后为每个子集生成排列。 –

std :: next_permutation和std :: prev_permutation – pat

投票关闭，因为缺乏可重复的示例 –

答

我们使用位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; 
}

此外，你可以只使用回溯采取阵列中的一个或多个元素来生成所有可能的排列生成每个子排列。

从集合中生成所有可能的有序子集

相关推荐