/* Warm - up Problem 0B: Random Subsets
There are 2^n possible subsets of a set of n elements
(Two possibilities for each of the n members : in or out).
That's growing exponentially, so it can take a very long time print
them to a list. What if instead of generating all possible subsets,
we just generate a few random subsets? That way, we can get a rough
sense for what the subsets look like.
To generate a random subset from a set we visit every element of the set,
one after the other, and flip a fair coin to decide whether or not to
include that element in the resulting subset.
As long as the coin tosses are fair, this produces a uniformly -
random subset of the given set.
Write a function
set randomSubsetOf(set& s);
that accepts as input a set and returns a random subset of that set.
Your algorithm should be recursive and not use any loops(for, while, etc.) */
#include
using std::set;
#include
using std::cin;
using std::cout;
#include
using std::vector;
vector< set > subsetsOf(set& s);
int main() {
int ints[] = { 10,20 };
set values(ints, ints + 2);
for (set subset : subsetsOf(values)) {
for (int i : subset) {
cout << i << " ";
}
cout << '\n';
}
cin.get();
}
vector< set > subsetsOf(set& s) {
if (s.empty()) { //base case
vector< set > result;
result.push_back(s);
return result;
}
else {
set::iterator itr = s.begin();
int elem = *itr;
s.erase(elem);
set rest = s;
vector< set > result;
for (set s : subsetsOf(rest)) {
result.push_back(s);
s.insert(elem);
result.push_back(s);
}
return result;
}
}