Generating combinations in C++

Question

I have been searching for a source code for generating combinations using C++. I found some advanced codes for this but that is good for only specific number predefined data. Can anyone give me some hints, or perhaps, some ideas to generate a combination?

As an example, suppose the set S = { 1, 2, 3, ...., n} and we pick r= 2 out of it. The input would be n and r. In this case, the program will generate arrays of length two. So input of 5 2 would output 1 2, 1 3.

I had difficulty in constructing the algorithm. It took me a month to think about this.

Underlie

I don't really understand what you want. Given the set S and input 2 do you want all the combinations of 2 and each item of S in an array of array length 2? – Dwaynedweck

You need to be more specific what kind of combinations you want. For example, with S = {1, 2} and r=2, do you want {1,2} and {2,1}, or also {1,1} and {2,2}, or even just {1,2}? – Thong

I think he wants this: en.wikipedia.org/wiki/Combination. {1,2} {2,1} are the same, and {1,1} and {2,2} are not possible. – Exophthalmos

For readable algorithms, you can look in the Python documentation: docs.python.org/library/itertools.html – Barcus

The answer is one google search away – Entrust

there is an elaborate answer here #128204 – Doubletalk

If I understand correctly, you're looking for a kind of generic algorithm, right? With r=2, you only have two nested loops, but with r=3, you'd have three, so that would basically be a different algorithm, and you're looking for a single algorithm that handles all cases up to r=count. Right? Is that your question? – Extravert

Yes, @MrLister. I am looking for a single algorithm in C++ where the output when we enter n be the number of elements in the set and r be the length of the array. – Underlie

I am not concerned about the permutation, any how, this is what I wanted to know: if we enter n= 5; that is 1,2 ,3 ,4 5. and r = 1 we got the output 1,2,3,4,5. but if r=5, then we have 1 2 3 4 5. changing the inputs n= 5 r= 2, we have : 1 2 , 1 3, 1 4, 1 5 , 2 3 , etc... where we can check using the formula for combination.. – Underlie

I don't think the accepted answer is a choice. – Delldella

Answer 1

A simple way using std::next_permutation:

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

int main() {
    int n, r;
    std::cin >> n;
    std::cin >> r;

    std::vector<bool> v(n);
    std::fill(v.end() - r, v.end(), true);

    do {
        for (int i = 0; i < n; ++i) {
            if (v[i]) {
                std::cout << (i + 1) << " ";
            }
        }
        std::cout << "\n";
    } while (std::next_permutation(v.begin(), v.end()));
    return 0;
}

or a slight variation that outputs the results in an easier to follow order:

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

int main() {
   int n, r;
   std::cin >> n;
   std::cin >> r;

   std::vector<bool> v(n);
   std::fill(v.begin(), v.begin() + r, true);

   do {
       for (int i = 0; i < n; ++i) {
           if (v[i]) {
               std::cout << (i + 1) << " ";
           }
       }
       std::cout << "\n";
   } while (std::prev_permutation(v.begin(), v.end()));
   return 0;
}

A bit of explanation:

It works by creating a "selection array" (v), where we place r selectors, then we create all permutations of these selectors, and print the corresponding set member if it is selected in in the current permutation of v.

Ammamaria

It will output permutations and not combinations as it was stated in the question. You may find this link helpful – Bissextile

I tried it, it outputs nested loop (reverse), something like <code>for (int n = 5; n >= 1; --n) for (int m = n - 1; m >= 1; --m) cout << n << m</code> – Decemvir

hm. either I miss something or you miss something. check this out: ideone.com/tfAGp – Ammamaria

This code is correct and it does produce combinations. The reason it works is because it prints all the sorted permutations. – Wagonette

@mitchnull, Thank you for the code. It is actually correct and it does generate combinations. although I don't fully understand the algorithm; what could be the running time of this algorithm? – Underlie

std::next_permutation performs at most n/2 swaps. The outer loop runs Cr(n, r) times, and we also have an inner loop that's O(n). – Ammamaria

I rewrote this code in a generic form: coliru.stacked-crooked.com/… – Shirleeshirleen

You can get that "easier to follow order" without inverting if(v[i]) check if you fill v from v.begin() to v.end()-n+r instead of v.begin()+n-r to v.end(). – Compensation

@Compensation are you sure? that'd mean 1 1 1 0 0 (for example, for inputs n=5 r=3) for the starting set, and next_permutation would be 0 0 1 1 1 (which would be lexicographically smaller), so the loop would stop after the first iteration... – Ammamaria

Ah, right, you'd also have to use prev_permutation in that case. – Compensation

@Compensation Eh, indeed. I haven't thought of using prev_permutation ;) Will update the answer, thanks. – Ammamaria

Answer 2

You can implement it if you note that for each level r you select a number from 1 to n.

In C++, we need to 'manually' keep the state between calls that produces results (a combination): so, we build a class that on construction initialize the state, and has a member that on each call returns the combination while there are solutions: for instance

#include <iostream>
#include <iterator>
#include <vector>
#include <cstdlib>

using namespace std;

struct combinations
{
    typedef vector<int> combination_t;

    // initialize status
   combinations(int N, int R) :
       completed(N < 1 || R > N),
       generated(0),
       N(N), R(R)
   {
       for (int c = 1; c <= R; ++c)
           curr.push_back(c);
   }

   // true while there are more solutions
   bool completed;

   // count how many generated
   int generated;

   // get current and compute next combination
   combination_t next()
   {
       combination_t ret = curr;

       // find what to increment
       completed = true;
       for (int i = R - 1; i >= 0; --i)
           if (curr[i] < N - R + i + 1)
           {
               int j = curr[i] + 1;
               while (i <= R-1)
                   curr[i++] = j++;
               completed = false;
               ++generated;
               break;
           }

       return ret;
   }

private:

   int N, R;
   combination_t curr;
};

int main(int argc, char **argv)
{
    int N = argc >= 2 ? atoi(argv[1]) : 5;
    int R = argc >= 3 ? atoi(argv[2]) : 2;
    combinations cs(N, R);
    while (!cs.completed)
    {
        combinations::combination_t c = cs.next();
        copy(c.begin(), c.end(), ostream_iterator<int>(cout, ","));
        cout << endl;
    }
    return cs.generated;
}

test output:

1,2,
1,3,
1,4,
1,5,
2,3,
2,4,
2,5,
3,4,
3,5,
4,5,

Decemvir

Answer 3

my simple and efficient solution based on algorithms from Prof. Nathan Wodarz:

// n choose r combination
#include <vector>
#include <iostream>
#include <algorithm>

struct c_unique {
  int current;
  c_unique() {current=0;}
  int operator()() {return ++current;}
} UniqueNumber;

void myfunction (int i) {
  std::cout << i << ' ';
}

int main()
{
    int n=5;
    int r=3;

    std::vector<int> myints(r);
    std::vector<int>::iterator first = myints.begin(), last = myints.end();

    std::generate(first, last, UniqueNumber);

    std::for_each(first, last, myfunction);
    std::cout << std::endl;

    while((*first) != n-r+1){
        std::vector<int>::iterator mt = last;

        while (*(--mt) == n-(last-mt)+1);
        (*mt)++;
        while (++mt != last) *mt = *(mt-1)+1;

        std::for_each(first, last, myfunction);
        std::cout << std::endl;
    }
}

then output is:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

Emelina

This is the fastest, simplest, and cleanest non-recursive algorithm. Recursion does not add clarity here and is probably slower. – Unloosen

It's only clean because it is hard-coded to work with values from 1 to N. Otherwise exactly the same as the more generic one of CapelliC. – Campestral

Answer 4

Below is an iterative algorithm in C++ that does not use the STL nor recursion nor conditional nested loops. It is faster that way, it does not perform any element swaps and it does not burden the stack with recursion and it can also be easily ported to ANSI C by substituting mallloc(), free() and printf() for new, delete and std::cout, respectively.

If you want the displayed elements to start from 1 then change the OutputArray() function.
Namely: cout << ka[i]+1... instead of cout << ka[i]....

Note that I use K instead of r.

void OutputArray(unsigned int* ka, size_t n) {
    for (int i = 0; i < n; i++)
        std::cout << ka[i] << ",";
    std::cout << endl;
}


void GenCombinations(const unsigned int N, const unsigned int K) {
    unsigned int *ka = new unsigned int [K];  //dynamically allocate an array of UINTs
    unsigned int ki = K-1;                    //Point ki to the last elemet of the array
    ka[ki] = N-1;                             //Prime the last elemet of the array.

    while (true) {
        unsigned int tmp = ka[ki];  //Optimization to prevent reading ka[ki] repeatedly

        while (ki)                  //Fill to the left with consecutive descending values (blue squares)
            ka[--ki] = --tmp;
        OutputArray(ka, K);

        while (--ka[ki] == ki) {    //Decrement and check if the resulting value equals the index (bright green squares)
            OutputArray(ka, K);
            if (++ki == K) {      //Exit condition (all of the values in the array are flush to the left)
                delete[] ka;
                return;
            }
        }
    }
}


int main(int argc, char *argv[])
{
    GenCombinations(7, 4);
    return 0;
}

Combinations: Out of "7 Choose 4".

Temporary

Allocating memory from heap is time expensive operation. With templates you can make it on stack. – Alternation

@DejanM: The stack memory is scarcer than heap memory. Anyway, note that the memory allocation happens only once. – Temporary

Answer 5

          #include<iostream>
          using namespace std;

          for(int i=1;i<=5;i++)
             for (int j=2;j<=5;j++) 
                if (i!=j)
                  cout<<i<<","<<j<<","<<endl;

           //or instead of cout... you can put them in a matrix n x 2 and use the solution

Extenuation

this includes different permutations of the same combination, try modify the 2nd loop for (int j=i+1;j<=5;j++) – Norfolk

r is a parameter, you can't just hard-code a double loop assuming r=2 – Par

Answer 6

Code is similar to generating binary digits. Keep an extra data structure, an array perm[], whose value at index i will tell if ith array element is included or not. And also keep a count variable. Whenever count == length of combination, print elements based on perm[].

#include<stdio.h>

// a[] : given array of chars 
// perm[] : perm[i] is 1 if a[i] is considered, else 0
// index : subscript of perm which is to be 0ed and 1ed
// n     : length of the given input array
// k     : length of the permuted string
void combinate(char a[], int perm[],int index, int n, int k)
{
   static int count = 0;

   if( count == k )
   { 
      for(int i=0; i<n; i++)
        if( perm[i]==1)
          printf("%c",a[i]);
      printf("\n");

    } else if( (n-index)>= (k-count) ){

         perm[index]=1;
         count++;
         combinate(a,perm,index+1,n,k);

         perm[index]=0;
         count--;
         combinate(a,perm,index+1,n,k);

   }
}
int main()
{
   char a[] ={'a','b','c','d'};
   int perm[4] = {0};
   combinate(a,perm,0,4,3);

   return 0;
}

Rosana

Answer 7

this is a recursive method, which you can use on any type. you can iterate on an instance of Combinations class (e.g. or get() vector with all combinations, each combination is a vector of objects. This is written in C++11.

//combinations.hpp
#include <vector>

template<typename T> class Combinations {
// Combinations(std::vector<T> s, int m) iterate all Combinations without repetition
// from set s of size m s = {0,1,2,3,4,5} all permuations are: {0, 1, 2}, {0, 1,3}, 
// {0, 1, 4}, {0, 1, 5}, {0, 2, 3}, {0, 2, 4}, {0, 2, 5}, {0, 3, 4}, {0, 3, 5},
// {0, 4, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, 
// {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}

public:
    Combinations(std::vector<T> s, int m) : M(m), set(s), partial(std::vector<T>(M))
    {
        N = s.size(); // unsigned long can't be casted to int in initialization

        out = std::vector<std::vector<T>>(comb(N,M), std::vector<T>(M)); // allocate space

        generate(0, N-1, M-1);
    };

    typedef typename std::vector<std::vector<T>>::const_iterator const_iterator;
    typedef typename std::vector<std::vector<T>>::iterator iterator;
    iterator begin() { return out.begin(); }
    iterator end() { return out.end(); }    
    std::vector<std::vector<T>> get() { return out; }

private:
    void generate(int i, int j, int m);
    unsigned long long comb(unsigned long long n, unsigned long long k); // C(n, k) = n! / (n-k)!

    int N;
    int M;
    std::vector<T> set;
    std::vector<T> partial;
    std::vector<std::vector<T>> out;   

    int count (0); 
};

template<typename T> 
void Combinations<T>::generate(int i, int j, int m) {  
    // combination of size m (number of slots) out of set[i..j]
    if (m > 0) { 
        for (int z=i; z<j-m+1; z++) { 
            partial[M-m-1]=set[z]; // add element to permutation
            generate(z+1, j, m-1);
        }
    } else {
        // last position
        for (int z=i; z<j-m+1; z++) { 
            partial[M-m-1] = set[z];
            out[count++] = std::vector<T>(partial); // add to output vector
        }
    }
}

template<typename T> 
unsigned long long
Combinations<T>::comb(unsigned long long n, unsigned long long k) {
    // this is from Knuth vol 3

    if (k > n) {
        return 0;
    }
    unsigned long long r = 1;
    for (unsigned long long d = 1; d <= k; ++d) {
        r *= n--;
        r /= d;
    }
    return r;
}

Test file:

// test.cpp
// compile with: gcc -O3 -Wall -std=c++11 -lstdc++ -o test test.cpp
#include <iostream>
#include "combinations.hpp"

struct Bla{
    float x, y, z;
};

int main() {

    std::vector<int> s{0,1,2,3,4,5};
    std::vector<Bla> ss{{1, .4, 5.0},{2, .7, 5.0},{3, .1, 2.0},{4, .66, 99.0}};

    Combinations<int> c(s,3);
    // iterate over all combinations
    for (auto x : c) { for (auto ii : x) std::cout << ii << ", "; std::cout << "\n"; }

    // or get a vector back
    std::vector<std::vector<int>> z = c.get();  

    std::cout << "\n\n";

    Combinations<Bla> cc(ss, 2);
    // combinations of arbitrary objects
    for (auto x : cc) { for (auto b : x) std::cout << "(" << b.x << ", " << b.y << ", " << b.z << "), "; std::cout << "\n"; }    

}

output is :

0, 1, 2, 0, 1, 3, 0, 1, 4, 0, 1, 5, 0, 2, 3, 0, 2, 4, 0, 2, 5, 0, 3, 4, 0, 3, 5, 0, 4, 5, 1, 2, 3, 1, 2, 4, 1, 2, 5, 1, 3, 4, 1, 3, 5, 1, 4, 5, 2, 3, 4, 2, 3, 5, 2, 4, 5, 3, 4, 5,

(1, 0.4, 5), (2, 0.7, 5), (1, 0.4, 5), (3, 0.1, 2), (1, 0.4, 5), (4, 0.66, 99), (2, 0.7, 5), (3, 0.1, 2), (2, 0.7, 5), (4, 0.66, 99), (3, 0.1, 2), (4, 0.66, 99),

Imbecility

Answer 8

I'd suggest figuring out how you would do it on paper yourself and infer pseudocode from that. After that, you only need to decide the way to encode and store the manipulated data.

For ex:

For each result item in result array // 0, 1, ... r
    For each item possible // 0, 1, 2, ... n
        if current item does not exist in the result array
            place item in result array
            exit the inner for
        end if
    end for
end for

Vo

Answer 9

You can use recursion whereby to pick N+1 combinations you pick N combinations then add 1 to it. The 1 you add must always be after the last one of your N, so if your N includes the last element there are no N+1 combinations associated with it.

Perhaps not the most efficient solution but it should work.

Base case would be picking 0 or 1. You could pick 0 and get an empty set. From an empty set you can assume that iterators work between the elements and not at them.

Impale

Answer 10

Here are my attempt:

Function (ready for copy/paste) without any dependency

 template<class _Tnumber, class _Titerator >
      bool next_combination
       (
            _Titerator const& _First
          , _Titerator const& _Last
          , _Tnumber const& _Max //!< Upper bound. Not reachable
       )
       {
        _Titerator _Current = _First;
         if( _Current  == _Last )
          {
           return false;
          }
         *_Current += 1;
         if( *_Current < _Max )
          {
           return true;
          }
        _Titerator _Next = _Current + 1;
         if( _Next == _Last )
          {
           return false;
          }
         if( false == next_combination( _Next, _Last, _Max - 1 ) )
          {
           return false;
          }
         *_Current = *_Next + 1; 
         return *_Current < _Max;
        }

Test:

vector<int> vec({3,2,1}); // In descending order and different
do
 {
  copy( vec.begin(), vec.end(), ostream_iterator<int>(cout, ", " ) ); cout << endl;
 }while( ::math::algorithm::next_combination( vec.begin(), vec.end(), 6 ) );

And output:

3, 2, 1,
4, 2, 1,
5, 2, 1,
4, 3, 1,
5, 3, 1,
5, 4, 1,
4, 3, 2,
5, 3, 2,
5, 4, 2,
5, 4, 3,

Alternation

Believe it or not, but all of your first code chunk violates the spec. No capitals after underscore at the beginning of a name; implementation reserved. – Komarek

Answer 11

One can directly compute all combinations indices in lexicographical order, like I did in following code.

These indices can be used for direct output or as pointers to any combined items as "abcde" string in second example of main() function, see output example after code.

Try it online!

#include <vector>
#include <iostream>

template <typename F>
void Combinations(size_t n, size_t k, F && out) {
    if (k > n)
        return;
    std::vector<size_t> a(k);
    for (size_t i = 0; i < k; ++i)
        a[i] = i;
    while (true) {
        out(a);

        int i = int(k) - 1;
        while (i >= 0 && a[i] >= n - 1 - (k - 1 - i))
            --i;
        if (i < 0)
            break;
        for (size_t j = a[i] + 1; i < k; ++j, ++i)
            a[i] = j;
    }
}

int main() {
    Combinations(5, 3, [](auto const & a){
        for (auto i: a)
            std::cout << i << " ";
        std::cout << std::endl;
    });

    std::string s = "abcde";
    Combinations(5, 3, [&](auto const & a){
        for (auto i: a)
            std::cout << s[i] << " ";
        std::cout << std::endl;
    });
}

Output:

0 1 2 
0 1 3 
0 1 4 
0 2 3 
0 2 4 
0 3 4 
1 2 3 
1 2 4 
1 3 4 
2 3 4 

a b c 
a b d 
a b e 
a c d 
a c e 
a d e 
b c d 
b c e 
b d e 
c d e 

Psychodrama

Answer 12

void print(int *a, int* s, int ls)
{
    for(int i = 0; i < ls; i++)
    {
        cout << a[s[i]] << " ";
    }
    cout << endl;
}    
void PrintCombinations(int *a, int l, int k, int *s, int ls, int sp)
{
   if(k == 0)
   {
       print(a,s,ls);
       return;
   }
   for(int i = sp; i < l; i++)
   {

      s[k-1] = i;
      PrintCombinations(a,l,k-1,s,ls,i+1);
      s[k-1] = -1;

   }
}

int main()
{
 int e[] = {1,2,3,4,5,6,7,8,9};
 int s[] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
 PrintCombinations(e,9,6,s,6,0);
}

Lynseylynus

Answer 13

For the special case of (n choose r), where r is a fixed constant, we can write r nested loops to arrive at the situation. Sometimes when r is not fixed, we may have another special case (n choose n-r), where r is again a fixed constant. The idea is that every such combination is the inverse of the combinations of (n choose r). So we can again use r nested loops, but invert the solution:

// example 1: choose each 2 from given vector and apply 'doSomething'
void doOnCombinationsOfTwo(const std::vector<T> vector) {
   for (int i1 = 0; i1 < vector.size() - 1; i1++) {
      for (int i2 = i1 + 1; i2 < vector.size(); i2++) {
         doSomething( { vector[i1], vector[i2] });
      }
   }
}


// example 2: choose each n-2 from given vector and apply 'doSomethingElse'
void doOnCombinationsOfNMinusTwo(const std::vector<T> vector) {
   std::vector<T> combination(vector.size() - 2); // let's reuse our combination vector 
   for (int i1 = 0; i1 < vector.size() - 1; i1++) {
      for (int i2 = i1 + 1; i2 < vector.size(); i2++) {
         auto combinationEntry = combination.begin(); // use iterator to fill combination
         for (int i = 0; i < vector.size(); i++) {
            if (i != i1 && i != i2) {
               *combinationEntry++ = i;
            }
         }
         doSomethingElse(combinationVector);
      }
   }
}

Sprit

Answer 14

This seems readable and also it works for std::vector, std::list, std::deque or even static declared int intArray[]

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <list>
#include <set>
#include <iterator>

template<typename InputIt, typename T>
bool nextCombination(InputIt begin,
                     InputIt end,
                     T toElement) {
    /*
        Given sequence: 1 2 3 4 5
        Final sequence: 6 7 8 9 10

        -- Formally --
        Given sequence: 1 2 ... k-1 k
        Final sequence: (n-k+1) (n-k+2) ... (n-1) n

        lengthOfSubsequence = positionOf(5) - positionOf(1) = 5
        
        We look for an element that satisfies:
            seqeunce[pos] < n - k + pos

    */

    const auto lengthOfSubsequence = std::distance(begin, end);

    auto viewed_element_it = std::make_reverse_iterator(end);
    auto reversed_begin = std::make_reverse_iterator(begin);

    /*Looking for this element here*/

    while ((viewed_element_it != reversed_begin) && 
           (*viewed_element_it >= toElement -
                                  lengthOfSubsequence + 
                                  std::distance(viewed_element_it, reversed_begin))) {
        //std::distance shows position of element in subsequence here
        viewed_element_it++;
    }

    if (viewed_element_it == reversed_begin)
        return false;

    auto it = std::prev(viewed_element_it.base());

    /*
        Increment the found element. 
    The rest following elements we set as seqeunce[pos] = seqeunce[pos-1] + 1
    */

    std::iota(it, end, *it + 1);

    return true;
}

int main()
{
    std::list<int> vec = { 1, 2, 3 };

    do {
        std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
        std::cout << std::endl;
    } while (nextCombination(vec.begin(), vec.end(), 10));
}

Born

Answer 15

vector<list<int>> generate(int N, int K, int& count) {

    vector<list<int>> output;

    if(K == 1) {
        count = N;
        for(int i = 1; i <= N; i++) {
            list<int> l = {i};
            output.push_back(l);
        }
    } else {
        count = 0;
        int n;
        vector<list<int>> l = generate(N, K - 1, n);
        for(auto iter = l.begin(); iter != l.end(); iter++) {
            int last = iter->back();
            for (int i = last + 1; i <= N; ++i) {
                list<int> value = *iter;
                value.push_back(i);
                output.push_back(value);
                count++;
            }
        }
    }

    return output;
}

Foss

Answer 16

You can just use for loops if r is small, here r = 2, so two for loops:

unsigned int i, j, max=0;
for(i=1; i<=n; i++){
    for(j=i+1; j<=n; j++){
            int ans = (i & j);
            cout << i << " " << j << endl;     
     }
}

Persecution

should use recursion – Betrothed