广度优先组合

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

例如：给定一组元素{1,2,4}，输出结果应该如下（也是按照这个顺序 - 不一定是数值，但是元素值 - 首先应该输出层1一个元件），那么层2（两个元件），最后层3（三种元素））：

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

2017-10-17 Acreol

使用二进制计数器。每个元素对应一个位。 – AndyG

不是这样输出吗？（而不是每个层） '''{1} {2} {1,2} {4} {1,4} { 2,4} { 1,2,4}''' – Acreol

当然可以。但你能想出一种方法来存储每个子集的大小吗？然后打印后？https：//graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable – MFisherKDX

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的载体（如果您的无符号长期股票是64位）。任何较大的载体都应该重新考虑，因为这需要一段时间，因为这是O(2^n)。

基本上unsigned long long i的每一位代表在一个nums位置和它是否应该被添加到该组或没有。

来源

2017-10-17 04:36:11 N00byEdge

我实现了类似的东西，有什么办法摆脱这个事实，你必须创建对象来中间存储元素？（就像MFisherKDX所说的那样） – Acreol

最好的方法是使用'result.push_back（std :: move（elements））'来制作临时存储器，而不必复制你的数据，如果你担心的是关于集合的复制性能（不知道我们在这里谈论的数据量有多大）。你也可以使用'result.back（）'作为添加东西的临时集合。 – N00byEdge

'std :: vector > result（1 << nums.size（））''std :: set elements＆= result [i];'摆脱'push_back' – Jarod42

您可以使用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

来源

2017-10-17 08:57:17 Jarod42

广度优先组合

回答

相关问题