CODEWITHSUNDEEP
c++data-structures
sparta93
sparta93

Reputation: 3854

How to detect all possible subsets from a given vector?

I'm writing a function which should detect all possible subsets from a main vector and push them to another vector. The elements in the subsets are also added to each other before being pushed into the new vector(s1).

At the moment what my code does is the following.. For example, lets say myvec = {1,2,3}, then v1 = {1,3,6,2,5,3}. It only sums consecutive numbers. However I also want it to sum up combinations like 1 & 3 which would add a 4 to the vector v1. At the moment, I have not been able to modify my algorithm in a way that I can achieve that. Any help will be appreciated!

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

Upvotes: 1

Views: 304

Answers (1)

5gon12eder
5gon12eder

Reputation: 25419

One way to think about the power set of a given (ordered) set is to think of its elements (the subsets) as bit vectors where the n-th bit is set to 1 if and only if the n-th element from the set was chosen for this subset.

So in your example, you'd have a 3 bit vector that could be represented as an unsigned integer. You'd “count the bit vector” up from 0 (the empty set) to 7 (the entire set). Then, in each iteration, you pick those elements for which the respective bit is set.

As can be readily seen, the power set explodes rapidly which will make it impractical to compute explicitly for any set with more than a dozen or so elements.

Casting these thoughts into C++, we get the following.

#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;
}

You might want to use a std::unordered_set for the subset-sums instead of a std::vector to save the space (and redundant further processing) for duplicates.

The program outputs the numbers 0 (the empty sum), 1 (= 1), 2 (= 2), 3 (= 1 + 2), 3 (= 3), 4 (= 1 + 3), 5 (= 2 + 3) and 6 (= 1 + 2 + 3). We can make this more visual.

 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

Upvotes: 1

Related Questions