6
\$\begingroup\$

Here is my recursive implementation of a power set function in C++. One thing that concerns me is that I am iterating over the set of sets while modifying its size. The code nevertheless functions as desired. Any feedback would be highly appreciated.

#include <iostream>
#include <set>
#include <vector>

template <typename T>
void power_set(int i, const std::vector<T>& set, std::set<std::set<T>>& set_of_sets)
{
    if (i == set.size())
    {
        set_of_sets.emplace(std::set<T>());  // empty set
        return;
    }

    power_set(i + 1, set, set_of_sets);

    for (auto& subset : set_of_sets)
    {
        auto augmented_subset = subset;
        augmented_subset.insert(set[i]);
        set_of_sets.insert(augmented_subset);
    }

}

int main()
{
    std::vector<std::string> set = {"a", "b", "c"};
    std::set<std::set<std::string>> set_of_sets;
    power_set(0, set, set_of_sets);

    for (auto& subset : set_of_sets)
    {
        std::cout << "{";
        for (auto& i : subset) std::cout << i << ",";
        std::cout << "}\n";
    }
    std::cout << set_of_sets.size() << "\n";
}
\$\endgroup\$
3
\$\begingroup\$

The recursion - even simulated via std::stack - is indeed unnecessary. Each subset has a corresponding number in \$[0, 2^n)\$ with bits indicating presence of an element in the subset, and each number in \$[0, 2^n)\$ corresponds to a subset. Consider a pseudocode

Set power_set(Set& the_set)
{
    Set result;
    Integral n = the_set.size()
    for (i = 0; i < (1 << n); i++) {
        result.insert(make_subset(the_set, i);
    }
    return result;
}

Set make_subset(Set& the_set, Integral indicator)
{
    Set result;
    Integral n = the_set.size();
    for (i = 0; i < (1 << n); i <<= 1) {
        if (indicator & i) {
            result.insert(the_set[i]);
        }
    }
    return result;
}
\$\endgroup\$
2
\$\begingroup\$

Happens to work, but...

You had this concern:

One thing that concerns me is that I am iterating over the set of sets while modifying its size.

and you were right to be concerned about it. Let's look at what you were doing:

for (auto& subset : set_of_sets)
{
    auto augmented_subset = subset;
    augmented_subset.insert(set[i]);
    set_of_sets.insert(augmented_subset);
}

Here, the problematic line is:

    set_of_sets.insert(augmented_subset);

because you are inserting into the same set you are iterating over. Keeping in mind that sets are sorted, there are two possible cases:

  1. You are inserting into the set before your iterator.
  2. You are inserting into the set after your iterator.

In case #1, nothing bad will happen because the item you just added to the set will not affect future iterations.

In case #2, what will happen is that your loop will be extended, and later on in the loop you will reach the newly added set and attempt to augment it. The reason that it still works is that when you attempt to augment the newly added set, you will augment it with the same set[i] that you just added, resulting in the same set, and when you add it to set_of_sets it won't do anything because it is a duplicate item. But you will be wasting time.

Up to double the amount of work

How much time is wasted depends on the ordering of the input. With a sorted input, your newly added sets will always fall into case #1 above and you won't waste any time. If your input is sorted in reverse order, your newly added sets will always fall into case #2 and you will double the amount of time you spend, because every time through that loop the loop becomes double the size as when it started.

Using std::move

Additionally, aside from the previous issue, I found that your program was slower than it could have been because you are making a copy of your augmented set when inserting it into your set of sets. I added std::move like this:

set_of_sets.insert(std::move(augmented_subset));

and it sped up your program by 19% on an input set with 18 elements.

Rewrite

In this rewrite, I used a vector to hold the new sets so that they could be added in a separate loop. I also added std::move and used the idea from πάντα ῥεῖ to remove the extraneous augmented_subset variable.

Alternatively, you could simply sort your input vector and leave your code as is (other than the std::move), because your code does not do any additional work with sorted input.

template <typename T>
void power_set(int i, const std::vector<T>& set, std::set<std::set<T>>& set_of_sets)
{
    if (i == set.size())
    {
        set_of_sets.emplace(std::set<T>());  // empty set
        return;
    }

    power_set(i + 1, set, set_of_sets);

    std::vector<std::set<T>> new_sets;
    for (auto subset : set_of_sets)
    {
        subset.insert(set[i]);
        new_sets.push_back(std::move(subset));
    }
    for (auto& new_set : new_sets)
    {
        set_of_sets.insert(std::move(new_set));
    }
}
\$\endgroup\$
  • \$\begingroup\$ Is there any reason you don't move into the subset also? e.g. subset.insert(std::move(set[i])); \$\endgroup\$ – user11881 Jan 14 '17 at 14:56
  • \$\begingroup\$ @user11881 set[i] is still being used after the insertion, so it would be incorrect to move it. For example, on the next loop iteration you would try to insert set[i] again and it would be gone if you had moved it. \$\endgroup\$ – JS1 Jan 14 '17 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.