c++powerset

How to find the power set of a given set without using left shift bit?


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:


Solution

  • 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.