fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. void print(std::vector<int> const &input){
  6.       std::cout << '{';
  7.       for (int i = 0; i < input.size(); i++) {
  8. 		std::cout << input.at(i);
  9.         if (i < input.size() - 1)
  10.           std::cout << ", ";
  11.       }
  12.       std::cout << '}';
  13. }
  14. void printMany(std::vector< std::vector<int> > const &input)
  15. {
  16.     std::cout << '{';
  17. 	for (int i = 0; i < input.size(); i++) {
  18.       print(input.at(i));
  19.       if (i < input.size() - 1)
  20.         std::cout << ", ";
  21. 	}
  22.     std::cout << '}';
  23.     std::cout << '\n';
  24. }
  25. void printPairs(std::vector< std::vector<int> > const &input)
  26. {
  27. 	for (int i = 0; i < input.size(); i+=2) {
  28.       cout << '{';
  29.       print(input.at(i));
  30.       cout << ", ";
  31.       print(input.at(i + 1));
  32.       cout << "}\n";
  33. 	}
  34. }
  35.  
  36. std::vector< std::vector<int> > f(std::vector<int> const &A, int i, const std::vector<int> &left, const std::vector<int> &right) {
  37.   if (i == A.size() - 1 && right.empty())
  38.     return std::vector< std::vector<int> >{left, std::vector<int> {A[i]}};
  39.   if (i == A.size())
  40.     return std::vector< std::vector<int> > {left, right};
  41.  
  42.   std::vector<int> _left{ left };
  43.   _left.emplace_back(A[i]);
  44.   std::vector< std::vector<int> > result = f(A, i + 1, _left, right);
  45.   std::vector<int> _right{ right };
  46.   _right.emplace_back(A[i]);
  47.   std::vector< std::vector<int> > result1 = f(A, i + 1, left, _right);
  48.   result.insert( result.end(), result1.begin(), result1.end() );
  49.   return result;
  50. }
  51.  
  52. std::vector< std::vector<int> > powerset(std::vector<int> const &A, const vector<int>& prefix = vector<int>(), int i = 0) {
  53.   if (i == A.size())
  54.     return std::vector< std::vector<int> > {prefix};
  55.  
  56.   std::vector<int> _prefix(prefix);
  57.   _prefix.emplace_back(A[i]);
  58.   std::vector< std::vector<int> > result = powerset(A, _prefix, i + 1);
  59.   std::vector< std::vector<int> > result1 = powerset(A, prefix, i + 1);
  60.   result.insert( result.end(), result1.begin(), result1.end() );
  61.   return result;
  62. }
  63.  
  64. int main() {
  65.   std::vector<int> A{0, 1, 2};
  66.   std::vector< std::vector<int> > ps = powerset(A);
  67.   cout << "Powerset:\n";
  68.   printMany(ps);
  69.   cout << "\nResult:\n";
  70.   for (int i=0; i<ps.size(); i++){
  71.     if (ps.at(i).size() > 1){
  72.       std::vector<int> left{ps.at(i)[0]};
  73.       std::vector<int> right;
  74.       printPairs(f(ps.at(i), 1, left, right));
  75.     }
  76.   }
  77.   return 0;
  78. }
  79.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Powerset:
{{0, 1, 2}, {0, 1}, {0, 2}, {0}, {1, 2}, {1}, {2}, {}}

Result:
{{0, 1}, {2}}
{{0, 2}, {1}}
{{0}, {1, 2}}
{{0}, {1}}
{{0}, {2}}
{{1}, {2}}
https://ideone.com/NuXHf4
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!