Algotree > Algorithms > Numeric > Generating subsets (combinations) using permutations

Generating subsets (combinations) using permutations

The idea of this algorithm is to use permutations of a boolean array to generate combinations.
The set bit(s) in a permutation can be used to mask the position(s) of an array containing the elements.
Note : c++ next__permutation function generates the next lexicographically greater permutation.

Combinations_Using_Permutation

C++ : Generating combinations or subsets using permutations.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
typedef vector<vector<int>> VVI;

VVI GetCombinations (vector<int>& vec) {

     int sz = vec.size();
     vector<bool> buff(sz);
     vector<vector<int>> combinations;

     for (int r=0; r<=sz; r++) {

         fill(buff.begin()+r, buff.end(), true);

         do {
             vector<int> comb;
             for (int i=0; i<sz; i++) {
                 if (buff[i] == false) {
                     comb.push_back(vec[i]);
                 }
             }
             combinations.push_back(comb);
         } while ( next_permutation(buff.begin(), buff.end()) );

         fill(buff.begin(), buff.end(), false);
     }

     for (int i=0; i < combinations.size(); i++) {
         cout << "( ";
         for (int j=0; j < combinations[i].size(); j++) {
             cout << combinations[i][j] << " ";
         }
         cout << ")" << endl;
     }
     return combinations;
}

int main() {

    // This type of vector initialization needs support for c++11 in the compiler
    vector<int> vec = { 1, 2, 3, 4}; 
    vector<vector<int>> combinations = GetCombinations (vec);
    return 0;
}

Output

( )
( 1 )
( 2 )
( 3 )
( 4 )
( 1 2 )
( 1 3 )
( 1 4 )
( 2 3 )
( 2 4 )
( 3 4 )
( 1 2 3 )
( 1 2 4 )
( 1 3 4 )
( 2 3 4 )
( 1 2 3 4 )