Generating combinations in C++

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, 

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

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".

 #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 

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; } 

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),

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 

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.

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, 

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 

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); } 

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); } } } 

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)); } 

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; }