使用STL列出特定子集

Question

假设我有一个数字范围,比如{2,3,4,5},按顺序存储在a中std::vector v,并且我想列出所有可能的子集,以5结尾使用STL ...即:

2 3 4 5
2 3 5
2 4 5
3 4 5
2 5
3 5
4 5
5

(我希望我不要忘记任何:))

我试过用while(next_permutation(v.begin(),v.end()))但没想出想要的结果:)

有没有人有想法？

PS:那些已经完成谷歌代码堵塞2010年档案的人可能会认识到这一点:)

Answer 1

让我们关注打印所有子集的问题.如您所知,如果您有n元素向量,那么您将拥有2^n可能的子集.并非巧合,如果你有n-bit整数,那么最大存储值是2^n.如果将每个整数视为位向量,则迭代所有可能的值将给出所有可能的位子集.好吧,我们通过迭代整数免费获得子集!

假设向量不超过32个元素(超过40亿个可能的子集!),这段代码将打印向量的所有子集v(不包括空元素):

for (uint32_t mask =1; mask < (1<<v.size()); ++mask)
{
  std::vector<int>::const_iterator it = v.begin();
  for (uint32_t m =mask; m; (m>>=1), ++it)
  {      
    if (m&1) std::cout << *it << " ";
  }
  std::cout << std::endl;
}

我只是为矢量大小创建所有可能的位掩码,并遍历每一位; 如果它已设置,我打印适当的元素.

现在应用以某个特定数字结尾的规则是小菜一碟(通过在通过掩码循环时检查附加条件).优选地,如果向量中只有一个5,则可以将其交换到末尾并打印所有向量的子集而不使用最后一个元素.

我有效利用std::vector,const_iterator并且std::cout,这样使用STL正在解决您不妨考虑一下.如果我想出更多STLish,我会告诉你(好吧,但是如何,它只是迭代).您可以使用此功能作为STL解决方案的基准;-)

编辑:正如JørgenFogh指出的那样,如果你想对大型矢量进行操作,它不能解决你的子集蓝调问题.实际上,如果您想打印32个元素的所有子集,它将生成数TB的数据.如果你觉得受到常数32的限制,你可以使用64位整数,但你甚至不会遍历所有数字.如果您的问题只是回答了多少个所需的子集,那么您肯定需要另一种方法.STL也不会有太大帮助;-)