问题描述
尽管有许多示例说明如何生成集合的实际功率集,但我找不到关于迭代生成功率集的任何信息(如std::iterator
中所述).我之所以喜欢这样的算法,是因为我的基本集很大.由于n元素集的幂集具有2 ^ n个元素,因此在实际计算集合时会很快耗尽内存.那么,有什么方法可以为给定集合的幂集创建迭代器吗?甚至有可能吗?
While there are plenty of examples on how to generate the actual power set of a set, I can't find anything about iteratively (as in std::iterator
) generating the power set. The reason why I would appreciate such an algorithm is the size of my base set. As the power set of a n-element set has 2^n elements, I would quickly run out of memory when actually computing the set. So, is there any way to create an iterator for the power set of a given set? Is it even possible?
- 如果更简单,创建一个
int
集的迭代器就可以了-我可以将它们用作实际集/向量的索引. - 由于我实际上是在
std::vector
上工作,因此如有必要,可以进行随机访问
- If it would be easier, an iterator that creates sets of
int
s would be fine - I could use them as indices for the actual set/vector. - As I actually work on a
std::vector
, random access would be possible if neccessary
推荐答案
使用组合和排列的for_each_combination
可以轻松地遍历std::vector<AnyType>
的幂集的所有成员.例如:
Using for_each_combination
from Combinations and Permutations one can easily iterate through all members of the power set of a std::vector<AnyType>
. For example:
#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
的每个电源集成员,并执行函子,该函子仅计算访问次数并打印出当前电源集:
This visits each power set member of this vector
, and executes the functor, which simply counts the number of visits and prints out the current power set:
{}
{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,则需要进行以下更改:
The syntax I've used above is C++14. If you have C++11, you will need to change:
[&](auto first, auto last)
收件人:
[&](std::vector<int>::const_iterator first, std::vector<int>::const_iterator last)
如果您使用的是C ++ 98/03,则必须编写函子或函数来替换lambda.
And if you are in C++98/03, you will have to write a functor or function to replace the lambda.
for_each_combination
函数不分配额外的存储空间.这全部通过将vector
的成员交换到范围[v.begin(), v.begin()+k)
中来完成.每次调用for_each_combination
时,向量都会保持其原始状态.
The for_each_combination
function allocates no extra storage. This is all done by swapping members of the vector
into the range [v.begin(), v.begin()+k)
. At the end of each call to for_each_combination
the vector is left in its original state.
如果出于某种原因您想尽早退出" for_each_combination
,只需返回true
而不是false
.
If for some reason you want to "exit" the for_each_combination
early, simply return true
instead of false
.
这篇关于迭代计算集合或向量的幂集的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!