如何從給定的矢量中檢測所有可能的子集？

Question

我在寫一個函數，它應該檢測主矢量中所有可能的子集，並將它們推送到另一個矢量。在被推入新的矢量（s1）之前，子集中的元素也相互相加。

目前我的代碼的作用如下： 例如，可以說myvec = {1,2,3}，然後v1 = {1,3,6,2,5,3}。它只求和連續的數字。不過，我也希望它總結了像1 & 3這樣的組合，它將向矢量v1添加4。目前，我無法以我能達到的方式修改我的算法。任何幫助將不勝感激！考慮功率設定給定的（有序）組

for (k=0; k<myvec.size(); k++) { 
     total = 0; 
     for (m=k; m<int_vec.size(); m++) {   
      total += myvec[m]; 
      v1.push_back(total); 
     } 
    } 

Answer 1

的一種方式是認爲其要素（子集）作爲位向量，其中Ñ第位被設置爲1，當且僅如果該集合中選擇了該集合中的第012個元素。

所以在你的例子中，你將有一個3位向量，可以表示爲一個無符號整數。你會「計數位向量」從0（空集）到7（整個集合）。然後，在每次迭代中，選擇爲其設置相應位的那些元素。

可以很容易地看到，功率集快速爆炸，這將使得對於具有十多個元素的任何集合顯式計算是不切實際的。

將這些想法轉化爲C++，我們得到以下結果。

#include <climits>  // CHAR_BIT 
#include <iostream>  // std::cout, std::endl 
#include <stdexcept> // std::invalid_argument 
#include <type_traits> // std::is_arithmetic 
#include <vector>  // std::vector 

template<typename T> 
std::vector<T> 
get_subset_sums(const std::vector<T>& elements) 
{ 
    static_assert(std::is_arithmetic<T>::value, "T must be arithmetic"); 
    if (elements.size() > CHAR_BIT * sizeof(unsigned long)) 
    throw std::invalid_argument {"too many elements"}; 
    const std::size_t power_size {1UL << elements.size()}; 
    std::vector<T> subset_sums {}; 
    subset_sums.reserve(power_size); 
    for (unsigned long mask = 0UL; mask < power_size; ++mask) 
    { 
     T sum {}; 
     for (std::size_t i = 0; i < elements.size(); ++i) 
     { 
      if (mask & (1UL << i)) 
      sum += elements.at(i); 
     } 
     subset_sums.push_back(sum); 
    } 
    return subset_sums; 
} 


int 
main() 
{ 
    std::vector<int> elements {1, 2, 3}; 
    for (const int sum : get_subset_sums(elements)) 
    std::cout << sum << std::endl; 
    return 0; 
} 

您可能要使用的子集資金，而不是std::vector以保存副本的空間（和冗餘進一步處理）的std::unordered_set。程序輸出數字0（空總數），1（= 1），2（= 2），3（= 1 + 2），3（= 3），4（= 1 + 3）， 5（= 2 + 3）和6（= 1 + 2 + 3）。我們可以讓這個更加可視化。

mask  mask 
(decimal) (binary) subset  sum 
––––––––––––––––––––––––––––––––––––––––––––––––– 
0   000   {}   0 
1   001   {1}   1 
2   010   {2}   2 
3   011   {1, 2}  3 
4   100   {3}   3 
5   101   {1, 3}  4 
6   110   {2, 3}  5 
7   111   {1, 2, 3} 6