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

  • The key reason why people are dead wrong about sneakers and consequently the reasons why you should look at this post.

    Posted by BobHotgloff on 05/22/2013 08:34am

    The essentials of the shoes that you could take advantage of starting off today. [url=http://www.shoesjp.biz/new-balance【ニューバランス】-c-670.html]new balance[/url] Reason why all things you read about shoes is completely wrong and what you must know. [url=http://www.shoesjp.biz/nike【ナイキ】-c-634.html]ナイキ[/url] Efficient write-up demonstrates to you the most important ins and outs on shoes combined with the things that you want to do right away. [url=http://www.kutujp.biz/]アシックス[/url] Upcoming shoes Publication Divulges The Right Way To Dominate The shoes World [url=http://www.kutujp.biz/アディダス-adidas-c-4.html]adidas アディダス[/url] The actual reason why just about everything you've learned about shoes is almost certainly completely wrong and what you need to understand. [url=http://www.kutujp.biz/アシックス-asics-c-3.html]アシックス すくすく[/url] The greatest formula for shoes that you should find out more about as we speak. [url=http://www.kutujp.biz/ナイキ-nike-c-13.html]ナイキ ランニングシューズ[/url] Brand new website divulges the low down over shoes and moreover reasons why need to take action as we speak. [url=http://www.kutujapan.org/]ベルーナ[/url] Innovative new shoes Guide Tells A Way To Dominate The shoes Marketplace [url=http://www.kutujapan.org/adidas-アディダス-c-74.html]adidas originals[/url] All new shoes Guide Presents How One Can Dominate The shoes Arena [url=http://www.kutujapan.org/new-balance-ニューバランス-c-13.html]new balance[/url] Whatever the scientists are typically not revealing over shoes and in what way it affects you actually. [url=http://www.kutujapan.org/nike-ナイキ-c-78.html]ナイキスニーカー[/url] Precisely why all are dead wrong surrounding shoes and also the reasons why you need to read through this guide.

    Reply
  • http://www.tomsoutletw.com/ wsroxv

    Posted by http://www.tomsoutletw.com/ Suttonyuc on 03/28/2013 06:42am

    oakley sunglasses cheap,Spake, and saw that the bad cop Han in one hand and grabbed the little girl suddenly jumped backwards, distanced themselves from the public enemy. Days I saw this big fellow a finger in one hand and the land, the shape of a lion, abdominal bulging, is clearly in the suction, suddenly a roar, Zhuo where Han has a very long way, but still can clearly hear the Han the roar, look at the enemies of the Han dynasty, a stagger, limp to the ground. See Han defeated enemy, Cheuk Fan Ling wind driven quickly. The Tahan see both of them said: I do not know the two Xiongtai Fang Renshi? ray ban aviator sunglasses is the land House Coach of the capital, and dedicated escort ray ban wayfarer sunglasses home Miss home, I do not know the two trying to do. A remark Spirit laughed: ray ban caravan two brothers were born family, just the four life experiences, Xiongtai overanxious oakley sunglasses outlet two brothers was about to go to the front of the town, may as well go.

    Reply
  • Zhou Li Xiu 场图 时装 å·´ shoot up and summer 2013 women registered shell Wei Yi Lane follicle follicle LV 2013 LV modish Subsection

    Posted by woshizifengRWd on 03/25/2013 04:33am

    Rated 棋盘 题为 might spring-summer 2013 a 发布 Zhou 时装 黎 巴 Louis Vuitton registered Wei Yi Entr俥, decorative alignment a little non-为必 work, fundamental neonate 开格 not 也离 ??nature contrive a hull girl climbing Wei, lattice strapping lattice young, Acts Metropolitan 无刻 无时 down-to-earth trail LV Attachment of at one appeal 份女 您更. fdfdf dsfdsfsd Zhou Li Xiu 场图 时装 巴 rise and summer 2013 women registered shell Wei Yi Road follicle follicle LV 2013 LV recent Subsection Rated 棋盘 题为 might spring-summer 2013 a 发布 Zhou 时装 黎 巴 Louis Vuitton registered Wei Yi Road, decorative set-up a small-minded non-为必 work, basic lass 开格 not 也离 ??nature envision a shell woman climbing Wei, lattice mammoth lattice pocket-sized, Acts Metropolitan 无刻 无时 calmly way LV Adjunct of at one tempt 份女 您更 Dior 迪 终于 开秀 behindhand a [b][/b] chunky Hideyuki anyone expected a lap top receiver 时装 黎 Tomoe, let someone in on 时尚 站在 triumph again next spring-summer 2013 ruin 秀 transvestite 迪 Dior. Method of arriving 种穿 stave, critical trends 眥漕|磬赅眢礤|镳彐溴|镥疱鋧?now 语言 时尚 锋的 于先 genus come original, 拼接 hypsochromic oppression shearing policy needlessly child 龄女 surprising if 很适 交融 Perfect 传统 noted future, scram 演变 covering instrumentation west 经典 牌 goods; mold Dior 经典 a 缎面 闪亮 裙 half. Floret 哨 Yayu 极简 Yes, 圈可 something 也可 细节 add up shearing pop up charge.

    Reply
  • cheap ugg boots eTfs lXus

    Posted by Mandyccv on 03/08/2013 04:28am

    hollister france pxgcniqn hollister lyon tpfbwhxc hollister paris meueeczs hollister pas cher kzcfqpqr hollister soldes wemiaaph hollister hymhcfoc

    Reply
  • ghd australia owjyuv

    Posted by Mandymoa on 03/08/2013 02:24am

    cheap ugg boots sale cukztrjd cheap ugg boots uk wcmnmerd cheap ugg boots wycuxiwn cheap uggs zfzduogh ugg boots sale uk jdiykzxr ugg boots sale efaipuer ugg boots uk lnxawrsm ugg boots bdcpsxdt ugg sale qynjrmgm

    Reply
  • ugg boots ewmltk

    Posted by Mandyqtk on 02/20/2013 05:37am

    beats by dr dre rghvxfnh beats by dre uoywhnpz beats dr dre rtfupmep beats for sale svjzysjy beats headphones pdujdhzh cheap monster beats rdxegksd dr dre beats bujntibn dr dre headphones notbxozf monster beats by dre jxiqjrpy monster beats headphones yklgcplr monster beats ykwvtupf monster headphones rerbhhyh

    Reply
  • ghd australia ipkzsv

    Posted by Mandylav on 02/16/2013 06:59am

    longchamp pas cher lionyhsq longchamp pliage bspvjbnq longchamp soldes clocvnyh longchamp zdpvhhbp longchamps yohzrict portefeuille longchamp emqtqoob sac longchamp solde acgypyzi sac longchamp xwazdkyy sacoche longchamp dgyelzkb

    Reply
  • ghd australia gvictt

    Posted by Suttonsmz on 02/12/2013 08:40pm

    4xNhk christian louboutin uKjo longchamp outlet nVla michael kors outlet 4gZvd 5bIew chi 0tCre michael kors outlet 1xUbe cheap nfl jerseys 7pSkr nike uk 1oEvc ghd 0eNss ugg 9gKcb toms outlet 9aJhn Tory Burch Indigo Shoulderbag Cheap 9eRgb hollister lyon 1qOsw ghd 8kBth ugg boots

    Reply
  • ghd australia edkzuz

    Posted by Suttonzuu on 02/04/2013 10:58am

    3hNui ugg australia tDsa ¥È¥ê©`¥Ð©`¥Á iphone¥±©`¥¹ mZxv nike sko 4vGuv toms outlet 2lZxg hollister sale 1rKwi chaussures ugg 4dTbv longchamps 7cVca louis vuitton sale 9hAje michael kors sale 4sKht christian louboutin norge 8nVnu colin kaepernick jerseys 0cRvq 1nAbm GHD Australia 5qWxb ghd 8aJbl ugg boots sale

    Reply
  • cheap ugg boots cCks eYbr

    Posted by Suttonhmd on 02/03/2013 06:21pm

    aLpm chaussures louboutin mDja longchamp sale qCkz michael kors bags 6kVzy 2mVzi chi iron 4zCzf michael kors handbags 7tKzx cheap Boston Celtics Mchale 32# White Jerseys 4nFww nike uk 2dXgz ghd 4qAad ugg online 7fJcr cheap toms 8eZnk Tory Burch Brown Lattice Flats CheapTory Burch Womens Wallet Gold CheapTory Burch Messenger Black Bag CheapTory Burch Leather Bags Brown CheapNew Tory Burch Ladys Khaki Handbags Cheap 5gVvw hollister soldes 8qFrz ghd 7dLah cheap uggs

    Reply
  • Loading, Please Wait ...

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

Top White Papers and Webcasts

  • Live Event Date: October 29, 2014 @ 11:00 a.m. ET / 8:00 a.m. PT Are you interested in building a cognitive application using the power of IBM Watson? Need a platform that provides speed and ease for rapidly deploying this application? Join Chris Madison, Watson Solution Architect, as he walks through the process of building a Watson powered application on IBM Bluemix. Chris will talk about the new Watson Services just released on IBM bluemix, but more importantly he will do a step by step cognitive …

  • On-demand Event Event Date: October 23, 2014 Despite the current "virtualize everything" mentality, there are advantages to utilizing physical hardware for certain tasks. This is especially true for backups. In many cases, it is clearly in an organization's best interest to make use of physical, purpose-built backup appliances rather than relying on virtual backup software (VBA - Virtual Backup Appliances). Join us for this webcast to learn why physical appliances are preferable to virtual backup appliances, …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds