I want to extract all possible sub-sets of an array in C# or C++ and then calculate the sum of all the sub-set arrays' respective elements to check how many of them are equal to a given number.
What I am looking for is the algorithm. I do understand the logic here but I have not been able to implement this one by now.
Considering a set S
of N
elements, and a given subset, each element either does or doesn't belong to that subset. Therefore are 2^N
possible subsets (if you include the original and empty sets), and there is a direct mapping from the bits in the binary representation of x
between 0
and 2^N
to the elements in the x
th subset of S
.
Once you've worked out how to enumerate the elements of a given subset, adding the values is simple.
For finding subsets which equal a total t
for large N
, one optimisation might be to record those subsets which exceed t
, and not test any which are proper supersets of those. Testing whether set number x
is a superset of set y
can be achieved with a single bitwise operation and an integer comparison.
What you're looking for is called the power set. Rosetta Code has a lot of different implementations, but here's their C++ code (they use a vector instead of an array, but it should be pretty easy to translate).
#include <iostream>
#include <set>
#include <vector>
#include <iterator>
typedef std::set<int> set_type;
typedef std::set<set_type> powerset_type;
powerset_type powerset(set_type const& set)
{
typedef set_type::const_iterator set_iter;
typedef std::vector<set_iter> vec;
typedef vec::iterator vec_iter;
struct local
{
static int dereference(set_iter v) { return *v; }
};
powerset_type result;
vec elements;
do
{
set_type tmp;
std::transform(elements.begin(), elements.end(),
std::inserter(tmp, tmp.end()),
local::dereference);
result.insert(tmp);
if (!elements.empty() && ++elements.back() == set.end())
{
elements.pop_back();
}
else
{
set_iter iter;
if (elements.empty())
{
iter = set.begin();
}
else
{
iter = elements.back();
++iter;
}
for (; iter != set.end(); ++iter)
{
elements.push_back(iter);
}
}
} while (!elements.empty());
return result;
}
int main()
{
int values[4] = { 2, 3, 5, 7 };
set_type test_set(values, values+4);
powerset_type test_powerset = powerset(test_set);
for (powerset_type::iterator iter = test_powerset.begin();
iter != test_powerset.end();
++iter)
{
std::cout << "{ ";
char const* prefix = "";
for (set_type::iterator iter2 = iter->begin();
iter2 != iter->end();
++iter2)
{
std::cout << prefix << *iter2;
prefix = ", ";
}
std::cout << " }\n";
}
}
Output:
{ }
{ 2 }
{ 2, 3 }
{ 2, 3, 5 }
{ 2, 3, 5, 7 }
{ 2, 3, 7 }
{ 2, 5 }
{ 2, 5, 7 }
{ 2, 7 }
{ 3 }
{ 3, 5 }
{ 3, 5, 7 }
{ 3, 7 }
{ 5 }
{ 5, 7 }
{ 7 }
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With