廣度優先組合

找到給定組的所有廣度優先組合的最有效方法是什麼？例如：廣度優先組合

例如：給定一組元素{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

廣度優先組合

回答

相關問題