Combinations in C++

Introduction

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

The notations used in this article are:

  • n: The larger sequence from which r sequence is picked
  • r: The smaller sequence picked from n sequence
  • c: The formula for the total number of possible combinations of r picked from n distinct objects: n! / (r! (n-r)! )
Note: 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
AD
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  | AD
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 for combinations of any numbers of letters. Let me give you few more examples and now you can figure them out yourself.

Combinations of 3 letters from {A, B, C, D, E} (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} (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 that you would have noticed by now the number of times that 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.

Now, go on to the source code section.

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() is in char_comb_ex.cpp. I'll stop to mention that function. For now, your focus is on recursive_combination(), a template function that I wrote, using char_combination() as a guideline.

The function 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 n sequence, whereas r-prefix parameters are r sequence related. As a end user, you need not bother about those parameters. What you need to know is func. func is a function that you defined. If the combination function finds a combination recursively, a way the user can process each combination must exist. The solution is a function pointer that 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 know that it calls func whenever there is a different combination, and you just need to define the func() function to process the combination.

Note: func() should not write to the two iterators passed to it.

The typical way of filling out the parameters in n_column and r_column is always 0, loop is the number of elements in r sequence minus that of n sequence, func is the function pointer to your function. (nbegin and nend, 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 number of depth of 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 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 vector of integers is below

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

typedef vector::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 last iterators for the n sequence. And, r_begin and r_end are iterators for the r sequence. Equal is the prediate 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 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:

  • All the objects in the n sequence must be distinct.
  • For next_combination(), the r sequence must be initialised to the first r-th elements of 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 {1,2,3,4} before the first call.
  • As for prev_combination(), the r sequence must be initialised to the last r-th elements of 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.
  • The n sequence must not change thoughout the process of finding all the combinations; otherwise, results are wrong (makes sense, right?).
  • next_combination() and prev_combination() operate on data types with the == operator defined. This means that if you want to use next_combination() on sequences of objects instead of sequences of POD (Plain Old Data), the class from these objects are instantiated must have an overloaded == operator defined or you can use the prediate versions.

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

Return Value

When next_combination() returns false, no more next combination can be found; the r sequence remains unaltered. The same is true for prev_combination().

Some Information about next_combination() and prev_combination()

  • The n and r sequences need not be sorted to use next_combination() or prev_combination().
  • next_combination() and prev_combination() do not use any static variables, so it is all right to find combinations of another sequence of a different data type, even when the current finding of combinations of the current sequence has 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.

What You Can Do with next_combination()

With next_combination() and next_permutation() from the STL algorithms, you can find permutations!! The formula for total number of permutations of r sequence picked from n sequence is n!/(n-r)!

You can call next_combination() first and then next_permutation() iteratively. That way, you 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 a limitation for the above code exists. The n and r sequences must be sorted in ascending order to work. This is because next_permutation() will return false when it encounters the 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.

How to Prove They Are Distinct Permutations

You can use a set container class in STL. All the objects in the set container are always in sorted order and there are no duplicate objects. For uour purpose, you 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 an 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 that would be generated. Too many permutations may take ages to complete (partly due to working of the set container) or worse, you may run out of memory!

Note: I have written a Combinations in C++, Part 2 article which you may read if you are interested to find out more about computing combinations on multi-core machines and computing combinations with repeated elements.

Revision History

14 September 2009 - Added the example code

17 March 2008 - Added the finding combinations of vectors in the source code

26 November 2006: Source code changes and bugs fixed:

  • All functions are enclosed in 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 runs properly in Visual C++ 8.0, without disabling the checked iterator.
  • next_combination and prev_combination have prediates version.


About the Author

Wong Shao Voon

I guess I'll write here what I does in my free time, than to write an accolade of skills which I currently possess. I believe the things I does in my free time, say more about me.

When I am not working, I like to watch Japanese anime. I am also writing some movie script, hoping to see my own movie on the big screen one day.

I like to jog because it makes me feel good, having done something meaningful in the morning before the day starts.

I also writes articles for CodeGuru; I have a few ideas to write about but never get around writing because of hectic schedule.

Downloads

Comments

  • Another sweet problem

    Posted by Simon on 07/09/2012 06:04am

    I want to find all possible combination of letters and dot “.” Condition is that suppose if we have 2 letter "ab" then using "." in between them we can make combination as “a.b” Same for 3 letters "abc" we can make possible combination "a.bc", "ab.c" and "a.b.c" Same for 4 letter "abcd" we can make "a.bcd", "ab.cd", "abc.d", "a.b.cd", "a.b.c.d", "ab.cd", "ab.c.d", "a.bc.d" and "abc.d". For the above problem I have tried to make a c++ program to find all possible combinations for any number of letters but I haven't been able to find a good solution.

    Reply
  • Convert FLV to SWF

    Posted by 250baichi on 09/16/2009 05:49am

    I juest bought a Convert FLV to SWF --- Sharing Youtube video with folks On converting FLV to SWF, FLV to SWF Converter is relly the fantastic one. Using this tool, you can convert Youtube(.flv) video to swf and edit flv files before converting.

    Reply
  • Article not updated.

    Posted by CBasicNet on 12/03/2006 08:42pm

    Hi guys, do not read this article because it is not the updated one, it is still the old one. I'll report this to Codeguru webmaster.

    • Article is updated.

      Posted by CBasicNet on 12/04/2006 08:39pm

      Brad has resolved it for me. Thanks, Brad!

      Reply
    Reply
  • Combinations in C++ using numbers as input

    Posted by ComputerPublic on 11/24/2006 04:48pm

    Hi, I have used your combination for char, but when I tried changing it to integers, it did not work. Can you please show me how to make it work for numbers. Thanks. Ed.

    Reply
  • Bit Combinations

    Posted by Legacy on 09/11/2003 12:00am

    Originally posted by: Jimmy

    Hi, using your algorithms, I've generate combinations for the integers 1..20 : this gives over 1 million combos : thanks for that.
    My program needs to filter out some of these combinations eg. don't allow combinations which contain {2,3). No problem there but I want to increase the efficiency of my program both for memory usage and speed. I'm thinking of representing each combination as a bitset and using shift operations for comparisons and filtering out various combinations.
    Is there come way I can use your algoritm to come up with all the combinations of 1's and 0's for say 20 bits eg
    00000000000000000001 : 1
    00000000000000000011 : 1,2
    00000000000000000010 : 2
    00000000000000000111 : 1,2,3
    00000000000000000110 : 2,3
    00000000000000000101 : 1,3
    ....

    Reply
  • what about,,,

    Posted by Legacy on 09/01/2003 12:00am

    Originally posted by: jared

    what about reverse combos, ie BA, CB, etc.

    what about redundancies, ie AA, BB, CC, etc, in the case of unlimited pool.

    what about different variants on the letter, ie upper case, lower case, italic, bold, etc.


    Is there a general formula for this?

    Reply
  • Another method using array of bools

    Posted by Legacy on 07/01/2003 12:00am

    Originally posted by: Paul McKenzie

    I've posted another method that overcomes

    a) the problems of next_permutation returning false
    b) is non-recursive
    c) works for any type of data (since it is a template).

    In short, it uses a totally different approach in finding combinations using next_permutation.

    It is available here:
    http://www.codeguru.com/forum/attachment.php?s=&postid=721348

    The discussion is here:
    http://www.codeguru.com/forum/showthread.php?s=&threadid=241675

    Probably I will post an article on it in the near future.

    Paul McKenzie

    Reply
  • another algorithm for combinations

    Posted by Legacy on 05/27/2003 12:00am

    Originally posted by: raffael cavaliere

    I find it not good at all to use recursion when your "n" ie number of item in the collection is greater than 12 or 13. Stack errors are very easy to get when it occurs.
    I wrote a small method you can use this way :

    //JAVA

    int[] list = {0,1,2,3,4,5}; //first elements (set of 6)
    int n = 12; //number of items in the collection

    while {list != null)
    list = Clist(n, list);

    public final static int[] CList(int n, int a[])
    {
    for (int i = a.length - 1; i >= 0; i--)
    {
    if (a[i] < n - a.length + i)
    {
    a[i]++;

    for (int r = i + 1; r < a.length; r++)
    a[r] = a[r - 1] + 1;

    return a;
    }
    }
    return null;
    }

    Reply
  • Another point to mention!

    Posted by Legacy on 02/19/2003 12:00am

    Originally posted by: But

    What if the location of the letter is important. I.e ABC!=CBA.

    AAA
    AAB
    AAC
    ABA
    ABB
    ABC
    ACA
    ACB
    ACC
    BAA
    BAB
    BAC
    BBA
    BBB
    BBC
    BCA
    BCB
    BCC
    CAA
    CAB
    CAC
    CBA
    CBB
    CBC
    CCA
    CCB
    CCC

    Total = 27

    So if we can use n letters {A,B,C} and r rows then n^r

    Reply
  • Combinations Tutorial

    Posted by Legacy on 02/18/2003 12:00am

    Originally posted by: Big Al

    Hi Thanks for your effort, could you explain how to do the same thing in VB?

    Thanks
    Al van Heerden

    Reply
  • Loading, Please Wait ...

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • As all sorts of data becomes available for storage, analysis and retrieval - so called 'Big Data' - there are potentially huge benefits, but equally huge challenges...
  • The agile organization needs knowledge to act on, quickly and effectively. Though many organizations are clamouring for "Big Data", not nearly as many know what to do with it...
  • Cloud-based integration solutions can be confusing. Adding to the confusion are the multiple ways IT departments can deliver such integration...

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date