广度优先组合
问题描述:
找到给定组的所有广度优先组合的最有效方法是什么?例如:广度优先组合
例如: 给定一组元素{1,2,4},输出结果应该如下(也是按照这个顺序 - 不一定是数值,但是元素值 - 首先应该输出层1一个元件),那么层2(两个元件),最后层3(三种元素)):
1 2 4 1 2 1 4 2 4 1 2 4
答
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
位置和它是否应该被添加到该组或没有。
答
您可以使用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);
这样算下来的排列
- 假假假
- 真的假的假( - > 100 010 001)
- 真真假( - > 110 101 011)
- 真真真
如果你想保持空集,开始与循环i = 1
使用二进制计数器。每个元素对应一个位。 – AndyG
不是这样输出吗? (而不是每个层) '''{1} {2} {1,2} {4} {1,4} { 2,4} { 1,2,4}''' – Acreol
当然可以。但你能想出一种方法来存储每个子集的大小吗?然后打印后?https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable – MFisherKDX