I'm trying to figure out how to implement an algorithm to find a power set given a set, but I'm having some trouble. The sets are actually vectors so for example I am given Set<char> set1{ 'a','b','c' };
I would do PowerSet(set1);
and I would get all the sets
but if I do Set<char> set2{ 'a','b','c', 'd' };
I would do PowerSet(set2)
and I would miss a few of those sets.
Set<Set<char>> PowerSet(const Set<char>& set1)
{
Set<Set<char>> result;
Set<char> temp;
result.insertElement({});
int card = set1.cardinality();
int powSize = pow(2, card);
for (int i = 0; i < powSize; ++i)
{
for (int j = 0; j < card; ++j)
{
if (i % static_cast<int> ((pow(2, j)) + 1))
{
temp.insertElement(set1[j]);
result.insertElement(temp);
}
}
temp.clear();
}
return result;
}
For reference:
cardinality()
is a function in my .h where it returns the size of the set.insertElement()
inserts element into the set while duplicates are ignored.temp.insertElement(s[j])
then result.insertElement(temp)
is because result
is a set
of a set
and so I needed to create a temporary set to insert the elements into then insert it into result.clear()
is a function that empties the set.removeElem()
which removes that element specified if it exists, otherwise it'll ignore it.Your if
test is nonsense -- it should be something like
if ((i / static_cast<int>(pow(2,j))) % 2)
you also need to move the insertion of temp into result after the inner loop (just before the temp.clear()).
With those changes, this should work as long as pow(2, card) does not overflow an int
-- that is up to about card == 30 on most machines.