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;
Here, the problematic line is:
because you are inserting into the same set you are iterating over. Keeping in mind that sets are sorted, there are two possible cases:
- You are inserting into the set before your iterator.
- 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.
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:
and it sped up your program by 19% on an input set with 18 elements.
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
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
power_set(i + 1, set, set_of_sets);
for (auto subset : set_of_sets)
for (auto& new_set : new_sets)