虽然有很多关于如何生成集合的实际幂集的示例,但我找不到任何关于迭代(如 std::iterator
)生成幂集的信息。我之所以喜欢这样的算法是因为我的基集的大小。由于 n 元集合的幂集有 2^n 个元素,因此在实际计算集合时我会很快耗尽内存。那么,有没有办法为给定集合的幂集创建一个迭代器呢?有可能吗?
- 如果这样更容易,创建
int
集合的迭代器就可以了——我可以将它们用作实际集合/vector 的索引。 - 因为我实际在
std::vector
上工作,所以如果需要的话,随机访问是可能的
最佳答案
使用 for_each_combination
来自 Combinations and Permutations可以轻松地遍历 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
结束时 vector 保持其原始状态。
如果出于某种原因你想“退出” for_each_combination
早点,简单地返回true
而不是 false
.
关于c++ - 迭代计算集合或 vector 的幂集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25984609/