Skip to content

Instantly share code, notes, and snippets.

/powerset.cc

Created Jul 25, 2015
Embed
What would you like to do?
#include <algorithm>
#include <iostream>
#include <iterator>
#include <regex>
#include <string>
#include <vector>
using set_t = std::vector<std::string>;
std::vector<set_t> powerset(const set_t &set) {
std::vector<set_t> result {{}};
for (const std::string &item : set) {
std::size_t n = result.size();
for (std::size_t i = 0; i < n; ++i) {
set_t rset = result[i];
rset.push_back(item);
result.push_back(rset);
}
}
return result;
}
int main() {
const std::regex token_re("[(),\\s]+");
while (true) {
std::string input;
set_t set;
std::getline(std::cin, input);
if (input.length() == 0) {
break;
}
for (auto it = std::sregex_token_iterator(input.begin(), input.end(), token_re, -1);
it != std::sregex_token_iterator(); ++it) {
if (it->length() != 0) {
set.push_back(*it);
}
}
auto pset = powerset(set);
std::cout << '(';
for (auto it = pset.begin(); it != pset.end(); ++it) {
if (it != pset.begin()) {
std::cout << ' ';
}
std::cout << '(';
for (auto iit = it->begin(); iit != it->end(); ++iit) {
if (iit != it->begin()) {
std::cout << ' ';
}
std::cout << *iit;
}
std::cout << ')';
}
std::cout << ')' << std::endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.