广度优先组合

Question

找到给定集合的所有广度优先组合的最有效方法是什么？

例如：给定一组元素 {1,2,4}，输出应如下所示（也按此顺序 - 不一定是数值，但元素值 - 首先应该输出第 1 层（一个元素），然后是第 2 层（两个元素），最后是第 3 层（三个元素）：

1 2 4 1 2 1 4 2 4 1 2 4

Answer 1

std::vector<std::set<int>> enumerate_all_subsets(const vector <int> &nums) {
    std::vector<std::set<int>> result;
    for(auto i = 0ull; i < (1 << nums.size()); ++ i) {
        std::set<int> elements;
        for(auto k = 0; k < nums.size(); ++ k)
            if((i >> k) & 1)
                elements.insert(nums[k]);
        result.push_back(elements);
    }
    return result;
}

这将遍历大小最大为 63 的向量（如果您的 unsigned long long 是 64 位）。可能应该重新考虑任何更大的向量，因为这需要一段时间，因为这是 O(2^n).

基本上 unsigned long long i 的每一位代表 nums 中的一个位置，以及是否应该将其添加到集合中。

Answer 2

您可以使用 std::next_permutation:

template <typename T, typename F>
void BreadthFirstCombination(const std::vector<T>& v, F f)
{
    for (int i = 0; i != v.size() + 1; ++i) {
        std::vector<bool> mask(i, true);
        mask.resize(v.size(), false);
        do {
            f(v, mask);
        } while (std::prev_permutation(mask.begin(), mask.end()));
    }
}

用法也类似：

auto printer = [](const auto&v, const std::vector<bool>& mask)
{
    for (std::size_t i = 0; i != v.size(); ++i) {
        if (mask[i]) {
            std::cout << v[i] << " ";
        }
    }
    std::cout << std::endl;    
};
std::vector<int> v = {1, 2, 4};
BreadthFirstCombination(v, printer);

Demo

所以做

的排列

假假假
真假假 (-> 100 010 001)
真真假 (-> 110 101 011)
真真真

如果要保留空集，请从 i = 1

开始循环

广度优先组合

Breadth First Combination

c++

combinations

breadth-first-search