13,700,326 members
alternative version

#### Stats

272.6K views
74 bookmarked
Posted 12 Apr 2016
Licenced CPOL

# Combinations in C++

, 5 Jun 2018
An article on finding combinations

## Introduction

Combination is the way of picking a different unique smaller set from a bigger set, without regard to the ordering (positions) of the elements (in the smaller set). This article teaches you how to find combinations. First, I will show you the technique to find combinations. Next, I will go on to explain how to use my source code. The source includes a recursive template version and a non-recursive template version. At the end of the article, I will show you how to find permutations of a smaller set from a bigger set, using both `next_combination()` and `next_permutation()`.

Before all these, let me first introduce to you the technique of finding combinations.

## The Technique

• n: n is the larger sequence from which the r sequence is picked.
• r: r is the smaller sequence picked from the n sequence.
• c: c is the formula for the total number of possible combinations of r, picked from n distinct objects: n! / (r! (n-r)!).
• The ! postfix means factorial.

### Explanation

Let me explain using a very simple example: finding all combinations of 2 from a set of 6 letters {A, B, C, D, E, F}. The first combination is AB and the last is EF.

The total number of possible combinations is: n!/(r!(n-r)!)=6!/(2!(6-2)!)=15 combinations.

Let me show you all the combinations first:

```AB
AC
AE
AF
BC
BD
BE
BF
CD
CE
CF
DE
DF
EF```

If you can't spot the pattern, here it is:

```AB | AB
A  | AC
A  | AE
A  | AF
---|----
BC | BC
B  | BD
B  | BE
B  | BF
---|----
CD | CD
C  | CE
C  | CF
---|----
DE | DE
D  | DF
---|----
EF | EF```

The same thing goes to combinations of any number of letters. Let me give you a few more examples and then you can figure them out yourself.

Combinations of 3 letters from {A, B, C, D, E} (a set of 5 letters).

The total number of possible combinations is: 10

```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```

Combinations of 4 letters from {A, B, C, D, E, F} (a set of 6 letters).

The total number of possible combinations is: 15.

```A B C D
A B C E
A B C F
A B D E
A B D F
A B E F
A C D E
A C D F
A C E F
A D E F
B C D E
B C D F
B C E F
B D E F
C D E F```

I'm thinking if you would have noticed by now, the number of times a letter appears. The formula for the number of times a letter appears in all possible combinations is n!/(r!(n-r)!) * r / n == c * r / n. Using the above example, it would be 15 * 4 / 6 = 10 times. All the letters {A, B, C, D, E, F} appear 10 times as shown. You can count them yourself to prove it.

## Source Code Section

Please note that all the combination functions are now enclosed in the `stdcomb` namespace.

### The Recursive Way

I have made a recursive function, `char_combination()` which, as its name implies, takes in character arrays and processes them. The source code and examples of using `char_combination()` are in char_comb_ex.cpp. I'll stop to mention that function. For now, our focus is on `recursive_combination()`, a template function, which I wrote using `char_combination()` as a guideline.

The function is defined in combination.h as below:

```// Recursive template function
template <class RanIt, class Func>
void recursive_combination(RanIt nbegin, RanIt nend, int n_column,
RanIt rbegin, RanIt rend, int r_column,int loop, Func func)
{
int r_size=rend-rbegin;

int localloop=loop;
int local_n_column=n_column;

//A different combination is out
if(r_column>(r_size-1))
{
func(rbegin,rend);
return;
}
//===========================

for(int i=0;i<=loop;++i)
{
RanIt it1=rbegin;
for(int cnt=0;cnt<r_column;++cnt)
{
++it1;
}
RanIt it2=nbegin;
for(int cnt2=0;cnt2<n_column+i;++cnt2)
{
++it2;
}

*it1=*it2;

++local_n_column;

recursive_combination(nbegin,nend,local_n_column,
rbegin,rend,r_column+1,localloop,func);

--localloop;
}
}```

The parameters prefixed with '`n`' are associated with the n sequence, while the r-prefixed one are r sequence related. As an end user, you need not bother about those parameters. What you need to know is `func`. `func` is a function defined by you. If the combination function finds combinations recursively, there must exist a way the user can process each combination. The solution is a function pointer which takes in two parameters of type `RanIt` (stands for Random Iterator). You are the one who defines this function. In this way, encapsulation is achieved. You need not know how `recursive_combination()` internally works, you just need to know that it calls `func` whenever there is a different combination, and you just need to define the `func()` function to process the combination. It must be noted that `func()` should not write to the two iterators passed to it.

The typical way of filling out the parameters is `n_column` and `r_column` is always 0, `loop` is the number of elements in the r sequence minus that of the n sequence, and `func` is the function pointer to your function (`nbegin` and `nend`, and `rbegin` and `rend` are self-explanatory; they are the first iterators and the one past the last iterators of the respective sequences).

Just for your information, the maximum depth of the recursion done is r+1. In the last recursion (r+1 recursion), each new combination is formed.

An example of using `recursive_combination()` with raw character arrays is shown below:

```#include <iostream>
#include <vector>
#include <string>
#include "combination.h"

using namespace std;
using namespace stdcomb;

void display(char* begin,char* end)
{
cout<<begin<<endl;
}

int main()
{
char ca[]="123456";
char cb[]="1234";

recursive_combination(ca,ca+6,0,
cb,cb+4,0,6-4,display);
cout<<"Complete!"<<endl;
return 0;
}```

An example of using `recursive_combination()` with a vector of integers is shown below:

```#include <iostream>
#include <vector>
#include <string>
#include "combination.h"

typedef vector<int>::iterator vii;

void display(vii begin,vii end)
{
for (vii it=begin;it!=end;++it)
cout<<*it;
cout<<endl;
}

int main()
{
vector<int> ca;
ca.push_back (1);
ca.push_back (2);
ca.push_back (3);
ca.push_back (4);
ca.push_back (5);
ca.push_back (6);
vector<int> cb;
cb.push_back (1);
cb.push_back (2);
cb.push_back (3);
cb.push_back (4);

recursive_combination(ca.begin (),ca.end(),0,
cb.begin(),cb.end(),0,6-4,display);
cout<<"Complete!"<<endl;
return 0;
}```

### The Non-Recursive Way

If you have misgivings about using the recursive method, there is a non-recursive template function for you to choose (actually there are two).

The parameters are even simpler than the recursive version. Here's the function definition in combination.h:

```template <class BidIt>

bool next_combination(BidIt n_begin, BidIt n_end,
BidIt r_begin, BidIt r_end);

template <class BidIt>

bool next_combination(BidIt n_begin, BidIt n_end,
BidIt r_begin, BidIt r_end, Prediate Equal );```

And its reverse counterpart version:

```template <class BidIt>

bool prev_combination(BidIt n_begin, BidIt n_end,
BidIt r_begin, BidIt r_end);

template <class BidIt>

bool prev_combination(BidIt n_begin, BidIt n_end,
BidIt r_begin, BidIt r_end, , Prediate Equal );```

The parameters `n_begin` and `n_end` are the first and the last iterators for the n sequence. And, `r_begin` and `r_end` are iterators for the r sequence. `Equal` is the predicate for comparing equality.

You can peruse the source code for these two functions in combination.h and its examples in next_comb_ex.cpp and prev_comb_ex.cpp, if you want.

A typical way of using `next_combination` with raw character arrays is as below:

```#include <iostream>
#include <vector>
#include <string>
#include "combination.h"

using namespace std;
using namespace stdcomb;

int main()
{
char ca[]="123456";
char cb[]="1234";

do
{
cout<<cb<<endl;
}
while(next_combination(ca,ca+6,cb,cb+4));
cout<<"Complete!"<<endl;

return 0;
}```

A typical way of using `next_combination` with a vector of integers is as below:

```#include <iostream>
#include <vector>
#include <string>
#include "combination.h"

template<class BidIt>
void display(BidIt begin,BidIt end)
{
for (BidIt it=begin;it!=end;++it)
cout<<*it<<" ";
cout<<endl;
}

int main()
{
vector<int> ca;
ca.push_back (1);
ca.push_back (2);
ca.push_back (3);
ca.push_back (4);
ca.push_back (5);
ca.push_back (6);
vector<int> cb;
cb.push_back (1);
cb.push_back (2);
cb.push_back (3);
cb.push_back (4);

do
{
display(cb.begin(),cb.end());
}
while(next_combination(ca.begin (),ca.end (),cb.begin (),cb.end()) );

cout<<"Complete!"<<endl;

return 0;
}```

### Certain Conditions Must Be Satisfied In Order For next_combination() to Work

1. All the objects in the n sequence must be distinct.
2. For `next_combination()`, the r sequence must be initialized to the first r-th elements of the n sequence in the first call. For example, to find combinations of r=4 out of n=6 {1,2,3,4,5,6}, the r sequence must be initialised to {1,2,3,4} before the first call.
3. As for `prev_combination()`, the r sequence must be initialised to the last r-th elements of the n sequence in the first call. For example, to find combinations of r=4 out of n=6 {1,2,3,4,5,6}, the r sequence must be initialsed to {3,4,5,6} before the first call.
4. The n sequence must not change throughout the process of finding all the combinations, else results are wrong (makes sense, right?).
5. `next_combination()` and `prev_combination()` operate on data types with the `==` operator defined. That is to mean if you want to use `next_combination()` on sequences of objects instead of sequences of POD (Plain Old Data), the class from which these objects are instantiated must have an overloaded `==` operator defined, or you can use the predicate versions.

When the above conditions are not satisfied, results are undetermined even if `next_combination()` and `prev_combination()` may return `true`.

### Return Value

When `next_combination()` returns `false`, no more next combinations can be found, and the r sequence remains unaltered. Same for `prev_combination()`.

### Some Information About next_combination() and prev_combination()

1. The n and r sequences need not be sorted to use `next_combination()` or `prev_combination()`.
2. `next_combination()` and `prev_combination()` do not use any `static` variables, so it is alright to find combinations of another sequence of a different data type, even when the current finding of combinations of the current sequence have not reached the last combination. In other words, no reset is needed for `next_combination()` and `prev_combination()`.

Examples of how to use these two functions are in next_comb_ex.cpp and prev_comb_ex.cpp.

## So What Can We Do With next_combination()?

With `next_combination()` and `next_permutation()` from STL algorithms, we can find permutations!!

The formula for the total number of permutations of the r sequence, picked from the n sequence, is: n!/(n-r)!

We can call `next_combination()` first, then `next_permutation()` iteratively; that way, we will find all the permutations. A typical way of using them is as follows:

```sort(n.begin(),n.end());
do
{
sort(r.begin(),r.end());
//do your processing on the new combination here
do
{
//do your processing on the new permutation here
}
while(next_permutation(r2.begin(),r2.end()))
}
while(next_combination(n.begin(),n.end(),r.begin(),r.end() ));```

However, I must mention that there exists a limitation for the above code. The n and r sequences must be sorted in ascending order in order for it to work. This is because `next_permutation()` will return `false` when it encounters a sequence in descending order. The solution to this problem for unsorted sequences is as follows:

```do
{
//do your processing on the new combination here

for(cnt i=0;cnt<24;++cnt)
{
next_permutation(r2.begin(),r2.end());
//do your processing on the new permutation here
}
}
while(next_combination(n.begin(),n.end(),r.begin(),r.end() ));```

However, this method requires you to calculate the number of permutations beforehand.

## So How Do I Prove They Are Distinct Permutations?

There is a `set` container class in STL we can use. All the objects in the `set` container are always in sorted order, and there are no duplicate objects. For our purpose, we will use this `insert()` member function:

`pair <iterator, bool> insert(const value_type& _Val);`

The `insert()` member function returns a pair, whose `bool` component returns `true` if an insertion is made, and `false` if the `set` already contains an element whose key had an equivalent value in the ordering, and whose iterator component returns the address where a new element is inserted or where the element is already located.

proof.cpp is written for this purpose, using the STL `set` container to prove that the permutations generated are unique. You can play around with this, but you should first calculate the number of permutations which would be generated. Too many permutations may take ages to complete (partly due to the working of the `set` container), or worse, you may run out of memory!

## Improved Next Combination with State

To speed up `next_combination`, we can store the state of generated combination so that it does not have to find which current combination elements correspond to the bigger collection. One way to do it is to store this state inside a class but this violates the design of STL algorithms. Another way to do it, is to pass this state to `next_combination` at every call. The declaration of `next_combination` and `next_combination_with_state` are listed below so that we can compare them side by side. The 1st one is current `next_combination` and 2nd one is overloaded one with 5th parameter as equality predicate and the 3rd is the new `next_combination_with_state` which also has 4 parameters as 1st `next_combination` but the last 2 parameters are of `BidItIt` type which is iterator whose value type is `BidIt` iterator. In other words, `BidItIt` is iterator of iterator! By storing `BidIt` iterator of `n_begin` and `n_end` itself, I could save some time without finding the range of `r_begin` and `r_end` that corresponds to `n_begin` and `n_end`. We can expect performance gain of 4X to 10X, depending on how big n and r collection.

```// Plain old next_combination
template <class BidIt>
inline bool next_combination(
BidIt n_begin,
BidIt n_end,
BidIt r_begin,
BidIt r_end);

// Plain old next_combination with equality predicate
template <class BidIt, class Prediate>
inline bool next_combination(
BidIt n_begin,
BidIt n_end,
BidIt r_begin,
BidIt r_end,
Prediate Equal);

// New next_combination_with_state
// its state is stored in r_beginIT and r_endIT
// which iterators of BidIt iterators
template <class BidIt, class BidItIt>
inline bool next_combination_with_state(
BidIt n_begin,
BidIt n_end,
BidItIt r_beginIT,
BidItIt r_endIT);

// New next_combination_with_state does not have
// version with equality predicate because it compare
// with BidIt iterators, not elements which BidIt
// iterator pointed to.```

`next_combination_with_state` does not have version with equality predicate because it compare with `BidIt` iterators, not elements themselves.

I reproduce example of `next_combination` usage so that we can compare with the one of `next_combination_with_state`.

```#include<iostream>
#include<vector>
#include<string>
#include"combination.h"

using namespace std;
using namespace stdcomb;

// for use with next_combination examples!
template<class BidIt>
void display(BidIt begin,BidIt end)
{
for (BidIt it=begin;it!=end;++it)
cout<<*it<<" ";
cout<<endl;
}

//test next_combination() with iterators
int main()
{
vector<int> ca;
ca.push_back (1);
ca.push_back (2);
ca.push_back (3);
ca.push_back (4);
ca.push_back (5);
ca.push_back (6);
vector<int> cb;
cb.push_back (1);
cb.push_back (2);
cb.push_back (3);
cb.push_back (4);

do
{
display(cb.begin(),cb.end());
}
while(next_combination(ca.begin (),ca.end (),cb.begin (),cb.end()) );

cout<<"Complete!"<<endl;

return 0;
}```

The `next_combination_with_state` example is below. Instead of constructing a `vector` of integer for smaller collection, we construct `cbit`, a `vector` out of `ca` iterators. We also have a new `display2` function to display the result, the main difference, `it` iterator is dereferenced twice, instead of once in `display`. Note, we cannot dereference first before passing to `display` because `cbit.end()` cannot be dereferenced as it is the one past the last valid iterator. Previously, I tried putting `cbit.begin()` and `cbit.end()` result back to `cb`, an already allocated `vector`. I got back the same performance, back to square one. Only use `next_combination_with_state` when you are comfortable with having your result as iterators of iterators. Since `cbit` stores `ca` iterators, `ca` must be kept alive while you still have `cbit`, else you got dangling iterators. `next_combination_with_state` requires C++17 because it uses `reverse_iterator`.

```#include<iostream>
#include<vector>
#include<string>
#include"combination.h"

using namespace std;
using namespace stdcomb;

template<class BidItIt>
void display2(BidItIt begin, BidItIt end)
{
for (BidItIt it = begin; it != end; ++it)
cout << **it << " ";
cout << endl;
}

//test next_combination_with_state() with iterators
int main()
{
vector<int> ca;
ca.push_back (1);
ca.push_back (2);
ca.push_back (3);
ca.push_back (4);
ca.push_back (5);
ca.push_back (6);

vector< vector<int>::iterator > cbit;
vector<int>::iterator it = ca.begin();
for(; it!=ca.end()-2; ++it)
cbit.push_back(it);

do
{
display2(cbit.begin(), cbit.end());
}
while(next_combination_with_state(ca.begin (),ca.end (),cbit.begin (),cbit.end () ) );

cout<<"Complete!"<<endl;

return 0;
}```

If you are interested, you can proceed to read the second part of the article: Combinations in C++, Part 2.

## History

• 6th June 2018 - Added Improved Next Combination with State section.
• 14th September 2009 - Added the example code
• 21st February 2008 - Added the finding combinations of vectors in the source code
• 26th November 2006 - Source code changes and bug fixes
• All functions are enclosed in the `stdcomb` namespace
• Solved a bug in `prev_combination` that `!=` operator must be defined for the custom class, unless the data type is a POD
• `next_combination` and `prev_combination` now run properly in Visual C++ 8.0, without disabling the checked iterator
• `next_combination` and `prev_combination` have a predicates version
• 30th July 2003 - First release on CodeProject

## Share

 Software Developer (Senior) United States
C++ developer transitioning to Python

Right now, I am picking up DevOps skills at Pluralsight and pursuing CCNA certification. Stay tuned for my CCNA related article!

Coding Tidbit Blog

Latest blogpost: C++ – The Forgotten Trojan Horse by Eric Johnson

Yinyang Theory Blog

If you like unconventional wisdom based on Yinyang philosophy, hop over to read my Yinyang blog.

Latest blogpost: Fortune Telling: Good News or Bad News For You?

IT Certifications

• IT Infrastructure Library Foundational (ITIL v3)
• Scrum Alliance Certified Scrum Master (CSM)
• Certified Secure Software Lifecycle Professional (CSSLP)

View my certificates here.

## You may also be interested in...

 Pro

 Re: crashed why? thanks a lot Shao Voon Wong30-Jul-15 23:40 Shao Voon Wong 30-Jul-15 23:40
 Re: crashed why? thanks a lot calmman.yang30-Jul-15 23:46 calmman.yang 30-Jul-15 23:46
 Re: crashed why? thanks a lot Shao Voon Wong31-Jul-15 0:13 Shao Voon Wong 31-Jul-15 0:13
 Re: crashed why? thanks a lot calmman.yang4-Aug-15 23:20 calmman.yang 4-Aug-15 23:20
 what changes in code are required to use your Combinations in C++ for array of float numbers? Deepak Gawali9-Jan-14 17:26 Deepak Gawali 9-Jan-14 17:26
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Wong Shao Voon9-Jan-14 17:35 Wong Shao Voon 9-Jan-14 17:35
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Deepak Gawali10-Jan-14 0:14 Deepak Gawali 10-Jan-14 0:14
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Wong Shao Voon10-Jan-14 2:04 Wong Shao Voon 10-Jan-14 2:04
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Deepak Gawali11-Jan-14 3:04 Deepak Gawali 11-Jan-14 3:04
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Wong Shao Voon11-Jan-14 14:21 Wong Shao Voon 11-Jan-14 14:21
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Deepak Gawali12-Jan-14 1:24 Deepak Gawali 12-Jan-14 1:24
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Wong Shao Voon12-Jan-14 2:50 Wong Shao Voon 12-Jan-14 2:50
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Deepak Gawali12-Jan-14 23:45 Deepak Gawali 12-Jan-14 23:45
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Deepak Gawali13-Jan-14 0:32 Deepak Gawali 13-Jan-14 0:32
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Wong Shao Voon13-Jan-14 15:10 Wong Shao Voon 13-Jan-14 15:10
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Deepak Gawali13-Jan-14 18:23 Deepak Gawali 13-Jan-14 18:23
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Wong Shao Voon13-Jan-14 18:34 Wong Shao Voon 13-Jan-14 18:34
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Deepak Gawali13-Jan-14 20:54 Deepak Gawali 13-Jan-14 20:54
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Wong Shao Voon13-Jan-14 22:35 Wong Shao Voon 13-Jan-14 22:35
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Deepak Gawali13-Jan-14 23:25 Deepak Gawali 13-Jan-14 23:25
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Wong Shao Voon14-Jan-14 3:16 Wong Shao Voon 14-Jan-14 3:16
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Deepak Gawali14-Jan-14 18:36 Deepak Gawali 14-Jan-14 18:36
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Deepak Gawali31-Jan-14 0:47 Deepak Gawali 31-Jan-14 0:47
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Wong Shao Voon31-Jan-14 2:14 Wong Shao Voon 31-Jan-14 2:14
 Re: what changes in code are required to use your Combinations in C++ for array of float numbers? Deepak Gawali31-Jan-14 19:37 Deepak Gawali 31-Jan-14 19:37
 Last Visit: 31-Dec-99 18:00     Last Update: 18-Sep-18 12:56 Refresh 1234 Next »

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Web01-2016 | 2.8.180910.1 | Last Updated 6 Jun 2018
Article Copyright 2016 by Cake Processor