迭代计算集合或向量的幂集 [英] Iteratively calculate the power set of a set or vector

问题描述

尽管有许多示例说明如何生成集合的实际功率集，但我找不到关于迭代生成功率集的任何信息(如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 ints 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.

这篇关于迭代计算集合或向量的幂集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！