Power Set
8.4 Power Set: Write a method to return all subsets of a set.
- The power set intuitively represents all the possible subcombinations you can have in given set. In other words, the power set represents all possible combinations for k = 0...n, where n is the length of the set.
- The power set gross at pow(2, k), where k is the length of the set.
ex.
case 1: {} = P(0) (empty set); 2^0 = 1
case 2: {}, {a} = P('a'); 2^1 = 2
case n: {}, {a}, {b}, {ab} = P('ab'); 2^2 = 4
' ' a
' ' a b ab
' ' a b ab c ac bc abc
' ' a b ab c ac bc abc d ad bd abd cd acd bcd abcd
- Pascals triangle provides us the amount of combinations per level, for any 'choose'. The growth is exponential.
- Every additional case feeds on the previous cases by appending a additional unique element to the end of the string.
vector<string> power_set(string str) {
int size = pow(2, str.length());
vector<string> build;//(size);
build.push_back(" ");
if (str.length() >= 1) {
string temp(1, str[0]);
build.push_back(temp);
}
for (int i = 1; i < str.length(); i++) {
int cur_size = build.size();
for (int j = 0; j < cur_size; j++) {
string temp = build[j];
temp.insert(temp.end(), str[i]);
//print(build);
build.push_back(temp);
}
}
return build;
}
int main()
{
vector<string> p_set = power_set("a");
print(p_set);
p_set = power_set("ab");
print(p_set);
p_set = power_set("abc");
print(p_set);
p_set = power_set("abcd");
print(p_set);
p_set = power_set("abcde");
print(p_set);
}
Last modified 3yr ago