迭代计算功率集一集或矢量

虽然有很多关于如何生成的实际功率集一集的例子，我无法找到任何迭代产生的功率设置（如std::iterator）的。我会欣赏这种算法的原因是我的基本集的大小。由于n元素集合的幂集具有2^n个元素，因此在实际计算集合时，我会很快耗尽内存。那么，有没有办法为给定集的幂集创建一个迭代器？它甚至有可能吗？迭代计算功率集一集或矢量

如果它会更容易，创建套int s就可以了迭代器 - 我可以用它们作为评价实际设置/矢量。
正如我实际上是在一个std::vector工作，如果使用for_each_combination从Combinations and Permutations一个neccessary

来源

2014-09-22 wondering

使用'n'位的位，初始化为零。在每一步中，加上1进位，就好像该位表示一个“n”位整数。使用结果模式的零和1来确定哪些元素属于当前子集。重复，直到bitset达到全部1。如果'n <= 64'（或任何平台上可用的最大整数），则可以使用实际的整数变量来代替位集。 – 2014-09-22 23:41:01

谢谢@IgorTandetnik - 关于如何处理这个问题的常识，就是我没有足够努力去寻找？如果你将它添加为一个，我会高兴地接受这个答案。 – wondering 2014-09-22 23:45:14

可以很容易地通过电源集std::vector<AnyType>的所有成员进行迭代随机访问将是可能的。例如：

#include <vector> 
#include <iostream> 
#include "../combinations/combinations" 

int 
main() 
{ 
    std::vector<int> v{1, 2, 3, 4, 5}; 
    std::size_t num_visits = 0; 
    for (std::size_t k = 0; k <= v.size(); ++k) 
     for_each_combination(v.begin(), v.begin()+k, v.end(), 
      [&](auto first, auto last) 
      { 
       std::cout << '{'; 
       if (first != last) 
       { 
        std::cout << *first; 
        for (++first; first != last; ++first) 
         std::cout << ", " << *first; 
       } 
       std::cout << "}\n"; 
       ++num_visits; 
       return false; 
      }); 
    std::cout << "num_visits = " << num_visits << '\n'; 
}

此访问这个vector的每个发电机组成员，并执行函子，它只是计数的访问次数，并打印出当前的功率设置：

{} 
{1} 
{2} 
{3} 
{4} 
{5} 
{1, 2} 
{1, 3} 
{1, 4} 
{1, 5} 
{2, 3} 
{2, 4} 
{2, 5} 
{3, 4} 
{3, 5} 
{4, 5} 
{1, 2, 3} 
{1, 2, 4} 
{1, 2, 5} 
{1, 3, 4} 
{1, 3, 5} 
{1, 4, 5} 
{2, 3, 4} 
{2, 3, 5} 
{2, 4, 5} 
{3, 4, 5} 
{1, 2, 3, 4} 
{1, 2, 3, 5} 
{1, 2, 4, 5} 
{1, 3, 4, 5} 
{2, 3, 4, 5} 
{1, 2, 3, 4, 5} 
num_visits = 32

语法我上面使用的是C++ 14。如果你有C++ 11，你将需要改变：

[&](auto first, auto last)

到：

[&](std::vector<int>::const_iterator first, std::vector<int>::const_iterator last)

而如果你是在C++ 98/03，你将不得不写一个函子或函数来替换lambda。

for_each_combination函数不分配额外的存储空间。这全部通过将vector的成员交换到[v.begin(), v.begin()+k)范围内来完成。在每次调用for_each_combination结束时，矢量都保持其原始状态。

如果由于某种原因想要提早退出for_each_combination，只需返回true而不是false即可。

来源

2014-09-22 23:49:10

迭代计算功率集一集或矢量

回答

相关问题