Wikipedia defines combinations as:

In combinatorial mathematics, a combination is an un-ordered collection of unique elements. (An ordered collection is called a permutation.) Given S, the set of all possible unique elements, a combination is a subset of the elements of S. The order of the elements in a combination is not important (two lists with the same elements in different orders are considered to be the same combination). Also, the elements cannot be repeated in a combination (every element appears uniquely once); this is often referred to as “without replacement/repetition”. This is because combinations are defined by the elements contained in them, s the set {1, 1, 1} is the same as {1}. For example, from a 52-card deck any 5 cards can form a valid combination (a hand). The order of the cards doesn’t matter and there can be no repetition of cards.

Mathworld provides a more terse definition:

The number of ways of picking k unordered outcomes from n possibilities.

The **combinations of n elements chosen as k** is the number of unique ways of selecting

*k*elements from a set of

*n*.

From now on, by set of *n* I always mean one of the form *{1, 2, 3, …, n}*.

So, what are the ways of choosing *2* elements from a set of *4*, *{1, 2, 3, 4}*?

`{1, 2}`

{1, 3}

{1, 4}

{2, 3}

{2, 4}

{3, 4}

That’s *6* ways, but what is the general formula?

This is easily proved: for a set of *n*, there are *n* ways of choosing the first element, *n * (n – 1)* ways of choosing the first two elements, …, *n * (n – 1) * … * (n – k + 1)* ways of choosing the first *k* elements. Unfortunately, this will generate duplicate subsets: for every subset of *k* elements, this will generate all the *k!* permutations of the subset. So, we have to divide the total number of subsets (*n * (n – 1) * … * (n – k + 1)*) by the number of repetitions (*k!*). This yields exactly the formula noted above.

Combinations are an astoundingly wide-spread concept, and are used in every branch of mathematics and especially in the analysis of algorithms. This said, there’s only one thing you really **need** to know: how to apply the formula.

Look at the formula above, notice that there are exactly *k* factors in the nominator and *k* factors in the denominator. So, to remember the formula and easily apply it:

**P1**. Draw the fraction line.

**P2**. Above the line, write *k* terms of the form: *n*, *n - 1*, *n - 2*, ...

**P3**. Below the line, write *k* terms of the form: *1*, *2*, *3*, ...

And now for the **fun part**. How do you generate combinations? Look closely at the example above. First thing to note is that every combination is an array of *k* elements. Next, the first digit in every set is, basically, every digit between *1* and *n*. What about the other digits? They’re always between *1* and *n* and they’re always in ascending order. Now it should be obvious what the algorithm is:

**P1**. Start of with *(1, 2, ..., k)*; this is the first combination.

**P2**. Print it.

**P3**. Given the combination *(c _{0}, c_{1}, ..., c_{n})*, start from the back and for

*c*, if it is larger than

_{i}*n - k + 1 + i*then increment it and go on to the next indice

*i*. After this, if

*c*, then this is not a valid combination so we stop. Otherwise give

_{0}> n - k*c*the values of

_{i+1}, c_{i+2}, ...*c*. Jump to

_{i}+ 1, c_{i+1}+ 1, ...**P2**.

Here’s the sourcecode in C (comb1.c):

**NOTE:** Source is mangled by WordPress. Download the source file, or copy-paste it from here or remember to replace the amp-s with ampersands and the lt-s with “less then” signs.

#include <stdio.h> /* Prints out a combination like {1, 2} */ void printc(int comb[], int k) { printf("{"); int i; for (i = 0; i < k; ++i) printf("%d, ", comb[i] + 1); printf("\\b\\b}\\n"); } /* next_comb(int comb[], int k, int n) Generates the next combination of n elements as k after comb comb => the previous combination ( use (0, 1, 2, ..., k) for first) k => the size of the subsets to generate n => the size of the original set Returns: 1 if a valid combination was found 0, otherwise */ int next_comb(int comb[], int k, int n) { int i = k - 1; ++comb[i]; while ((i >= 0) && (comb[i] >= n - k + 1 + i)) { --i; ++comb[i]; } if (comb[0] > n - k) /* Combination (n-k, n-k+1, ..., n) reached */ return 0; /* No more combinations can be generated */ /* comb now looks like (..., x, n, n, n, ..., n). Turn it into (..., x, x + 1, x + 2, ...) */ for (i = i + 1; i < k; ++i) comb[i] = comb[i - 1] + 1; return 1; } int main(int argc, char *argv[]) { int n = 5; /* The size of the set; for {1, 2, 3, 4} it's 4 */ int k = 3; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */ int comb[16]; /* comb[i] is the index of the i-th element in the combination */ /* Setup comb for the initial combination */ int i; for (i = 0; i < k; ++i) comb[i] = i; /* Print the first combination */ printc(comb, k); /* Generate and print all the other combinations */ while (next_comb(comb, k, n)) printc(comb, k); return 0; }

Always open to comments. Have fun.

2007-10-22 at 15:41

[…] the full story here This entry was posted on Wednesday, October 17th, 2007 at 9:32 am and is filed under computer […]

2008-07-25 at 23:08

The explanation is good and crisp and the code is easy and good for a novice.

But like me, many others are looking for code/algorithm to generate combinations when we have repeated digits/numbers in a set. The code obviously doesn’t work in such a scenario

2009-11-12 at 18:35

Absolutely correct.

2010-06-20 at 3:21

Did you find any solutions elsewhere?

2010-10-08 at 17:08

@Kalpesh, @Thomas Dybdahl Ahle,

I have written an algorithm for this – combinations of a multiset – and placed it on my Web site here:

http://www.martinbroadhurst.com/combinatorial-algorithms.html

2011-06-26 at 19:16

That would be because “combinations”, by the mathematical defination, only have unique members. What you are wanting is permutations.

Off the top of my head, instead of seeding with comb[i] = comb[i – 1] + 1; , i think you could just use comb[i] = comb[0];

ie. instead of looping 1 2 3, 1 2 4, 1 2 5, 1 3 4. you’d skip to 1 3 1.

2008-08-05 at 9:42

@Kalpesh

Yes, it does.

If you want the set to contain elements different than {1, 2..}:

1. generate the set as I have

2. use the set elements as indexes into an array that contains the elements you want

For instance, suppose you’ve just generated for n=5, k=3:

comb=[0, 2, 4]

But you want the set to contain the elements:

set_elements=[9, 8, 7, 6, 5]

Instead of simply printing out comb[i], for i=1,2..k, print out set_elements[comb[i]] for i=1,2..k.

In my code, just change

printf(“%d, “, comb[i] + 1);

to

printf(“%d, “, set_elements[comb[i]]);

Hope this helps.

2009-11-12 at 18:28

This is good if the set:

set_elements=[9, 8, 7, 6, 5]

has the same amount of elements as ‘n’, and it doesnt work if you pass in less, like [4,2].

Even using set_elements[comb[i]%2] you start to get non-unique lists. :(

2008-08-15 at 12:54

Dear scvalex,

Thank you for your code, it has saved me a lot of head-scratching and time! Initially I had a stack corruption problem because the “while ((i >= 0) …” clause in next_comb could cause a problem if i was 0 when the following –i and ++comb[i] lines were executed. I changed the clause to “while ((i > 0) …” and this seemed to work fine.

Best regards,

Roy Harrison

2009-05-21 at 22:05

Correct me if I’m wrong, but i believe there is a minor bug here:

while((i >= 0) && (comb[i] >= n – k + 1 + i))

{

–i;

++comb[i];

}

The problem is the i >= 0. Letting ‘i’ be 0 in that condition will be followed by –i (making ‘i’ -1), which will be an invalid array index. The second part of the condition never seems to prevent i==0 from being executed.

Changing it to “i > 0″ removes the errant condition, and still appears to function as intended.

2013-04-13 at 15:32

Nice catch! I ported this to Go and it was crashing with an index out of bounds error.

2009-05-21 at 22:06

Ah, if I had only read Roy Harrison’s post first. He seems to have also discovered the same problem.

2009-05-25 at 23:47

What would be the algorithm for non-numeric elements, like set of {A,B,C,D,E,F}. Please let me know if I need to read some other material before I can understand this algorithm. I am a fairly good programmer.

2009-09-01 at 7:50

Great work dude, thanks a lot for your explanation and saves lot of time for fast programmers like me.

Wish you good luck mate.

2009-09-04 at 17:56

Interesting that if n=k, this only appears to generate the first combination of the sequence.

Greg

2009-09-04 at 18:13

Answered my own question

2009-10-21 at 19:44

I was working on this topic, trying to generate all combination once and store it for future requirement.

I tried adhoc approch(i.e. no smart algo), which let my program to run in out of memory state, then i recoded it to use secondary storage to store all combination, it took 104 min to generate all possible combination for 20 elements(of size 0 to 20).

well this algo seems like will solve my problem of optimization… will be implementing it in my solution soon.

(@ray,@luke)-nice find..

2010-04-21 at 12:33

Nice article.

I had to generate all ordered collections of

k elements picked from a set of n elements

with replacement/repetition, so I had to

adapt next_comb(). The code follows, I hope

that WordPress won’t make it unreadable

after formatting.

/*

next_comb(int comb[], int k, int n)

Generates the next combination after comb of k ordered elements

picked with repetition from a set of n

comb => the previous combination ( use (0, 0, 0, …, 0) for first)

k => the size of the subsets to generate

n => the size of the original set

Returns: 1 if a valid combination was found

0, otherwise

*/

int next_comb(int comb[], int k, int n) {

int i = k – 1;

++comb[i];

while(i > 0 && comb[i] >= n){

comb[i] = 0;

–i;

++comb[i];

}

if (comb[0] == n)

return 0; /* No more combinations can be generated */

return 1;

}

Note also that the initial combination in

main() should be changed to 0…0:

for (i = 0; i < k; ++i)

comb[i] = 0;

2010-04-21 at 13:06

Just noticed that WordPress has messed up the

predecrement operator in the while.

So, the –i was actually meant to be i=i-1

2010-07-20 at 15:15

what does amp and lt represent in next_comb() function?

2010-07-20 at 16:05

Oops, resolved. silly question

2010-07-23 at 4:58

I have been having some serious bed bug problems. Hopefully this will help me out so I can get rid of them.

2010-10-03 at 17:50

Hey thanks for helping me out with my assignment ;)

2010-10-28 at 17:55

This post helped me a lot. Thanks! :)

2010-10-31 at 1:00

[…] […]

2011-01-04 at 13:44

Helped me solve a problem for a friend of mine who is trying to generate a keyword list in PHP. Many thanks to the author! :)

2011-01-07 at 11:55

Hi there.

This is a nice piece on coding a combination generator. Your textual description looks very TAOCP, so I guess you borrowed it from Knuth’s The Art of Computer Programming, Volume 4A.

Kind regards

-K

2011-02-10 at 18:46

Hello there,

It is cool algorithm. Great works.

The same algorithm can be coded

recursively in much more naturally and

elegantly since the nature of the problem

is recursive.

The issue if the recursion is too deep,

then stack will blow up, i.e. choose 6

out 49. Also, it is more expensive than

the iterative version. But it is much

easier to understand the code; and

visualize the concept.

Regards

Duc Le

2011-02-21 at 19:22

Hi,

the following awk code also works:

BEGIN{

n = split(“a b c d e”, v, ” “)

comb(v, 4)

}

function comb(v, p){

for(i = 1; i <= p; i++){

k[i] = i

max[i] = n-(p-i)

}

while(1){

for(i = 1; i max[i] && –i)

;

if(k[1] > n-p+1)

break

for(; i < p; i++)

k[i+1] = k[i]+1

}

}

2011-03-26 at 20:01

Hi,

I have a question: Can I find (C(n,k))%M=? in optimal complexity ,when n=1,000,000,000 and M is prime?

Plz help me!!!

Thank you !!!

2011-03-26 at 20:03

L.E.: In O(1) time limit and 2MB memory limit

2011-05-27 at 11:13

I didn’t think too much, but if you need an approximate answer, you can use approximations about combinations, I guess. Otherwise, it seems tough!

2011-05-27 at 11:15

And, by the way, if M is relatively small, I suspect that you can find some algebraic properties that might help. It might not be O(1) though.

2011-06-18 at 17:02

hi,

what about if there is an array of n elements .& if we want to find sum of product of all k-elements at a time..

e.g. for n=3,k=2 & elements -a,b,c

sum=ab+bc+ca

plz reply..

2011-11-03 at 8:08

Healthy Skin Treatment Products…[…]Generating Combinations: 1 « Computer programming[…]…

2011-11-05 at 5:23

Network Blu-ray Disc Home Theater System 1100-Watt LG LHB335, Black…[…]Generating Combinations: 1 « Computer programming[…]…

2011-11-05 at 11:29

e-like.ro…[…]Generating Combinations: 1 « Computer programming[…]…

2011-12-02 at 8:32

security…[…]Generating Combinations: 1 « Computer programming[…]…

2012-01-04 at 19:15

#4 and #5 is right, so please fix your sourcecode.

2012-01-20 at 21:55

Here’s a recursive program to genrate the same………

#include

#include

int nCk(int n,int loopno,int ini,int *a,int k)

{

static int count=0;

int i;

loopno–;

if(loopno<0)

{

a[k-1]=ini;

for(i=0;i<k;i++)

{

printf("%d,",a[i]);

}

printf("\n");

count++;

return 0;

}

for(i=ini;i<=n-loopno-1;i++)

{

a[k-1-loopno]=i+1;

nCk(n,loopno,i+1,a,k);

}

if(ini==0)

return count;

else

return 0;

}

void main()

{

int n,k,*a,count;

printf("Enter the value of n and k\n");

scanf("%d %d",&n,&k);

a=(int*)malloc(k*sizeof(int));

count=nCk(n,k,0,a,k);

printf("No of combinations=%d\n",count);

}

2012-01-20 at 22:06

include stdio.h and stdlib.h in previous program.

2012-01-20 at 22:42

//Fixed a bug…….this one will work for nC0 also

#include

#include

#include

int nCk(int n,int loopno,int ini,int *a,int k)

{

if(k==0)

return 1;

static int count=0;

int i;

loopno–;

if(loopno<0)

{

a[k-1]=ini;

for(i=0;i<k;i++)

{

printf("%d,",a[i]);

}

printf("\n");

count++;

return 0;

}

for(i=ini;i<=n-loopno-1;i++)

{

a[k-1-loopno]=i+1;

nCk(n,loopno,i+1,a,k);

}

if(ini==0)

return count;

else

return 0;

}

void main()

{

int n,k,*a,count;

printf("Enter the value of n and k\n");

scanf("%d %d",&n,&k);

a=(int*)malloc(k*sizeof(int));

count=nCk(n,k,0,a,k);

printf("No of combinations=%d\n",count);

getch();

}

2012-04-04 at 10:45

Grilling…[…]Generating Combinations: 1 « Computer programming[…]…

2012-05-02 at 22:01

twitter…[…]Generating Combinations: 1 « Computer programming[…]…

2012-05-17 at 22:19

using NARS2000.32 , the old programming APL language:

z←a comb b

⎕IO←0

:if a ≤ 1

z←(b,1)[rho][iota]b

:else

z←⎕IO,1+(a-1) comb b-1

:if a ≤ b-1

z←z,[0]1+a comb b-1

:endif

:endif

2012-08-17 at 0:52

using NARS2000.32 , the old programming APL language:

Optimize 1 line and fast , also O(N)

Z<-{RightShoe}{IotaUnderbar}{Dieresis}{LeftShoe}[{Quad}IO]{CircleStile}(N{Rho}2){downTack}(-{Quad}IO)+{IotaUnderbar}K=(2{Star}N){UpArrow}{epsilon}Z{Jot}.+Z<-(({UpStile}N{ColonBar}2){Rho}2){Rho}Z{Jot}.+Z<-Z{Jot}.+Z<-Z{Jot}.+Z<-Z{Jot}.+Z<-0 1

2012-06-20 at 23:40

[…] […]

2012-06-23 at 21:41

I used this code, but when I entered values for 33 choose 5, the algorithm returned 237,736. The right answer is 376,922. So I started going backwards from there, 32/5, 31/5, 20/5, etc., and it returned all of the proper number of combinations. Is there something in the code that goes awry when “n” and “k” get to a certain value?

2012-07-18 at 16:31

Short and efficient code =

#include

void main(int argc, char *argv[]) {

int n = 5; /* The size of the set; for {1, 2, 3, 4} it’s 4 */

int k = 3; /* The size of the subsets; for {1, 2}, {1, 3}, … it’s 2 */

int comb[16] = {0}; /* comb[i] is the index of the i-th element in the combination */

int i = 0;

while (i >= 0) {

if (comb[i] < n + i – k + 1) {

comb[i]++;

if (i == k – 1) {

for (int j = 0; j < k; j++)

printf("%d ", comb[j]);

printf("\n");

}

else {

i++;

comb[i] = comb[i – 1];

}

}

else

i–;

}

}

NOTE: 33 choose 5, gives : C(5, 33) = (33!)/(28! x 5!) = 237,336

2012-07-18 at 23:08

#include

void main(int argc, char *argv[]) {

const int n = 5; /* The size of the set; for {1, 2, 3, 4} it’s 4 */

const int k = 3; /* The size of the subsets; for {1, 2}, {1, 3}, … it’s 2 */

int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */

int i = 0;

while (i >= 0) {

if (comb[i] < n + i – k + 1) { comb[i]++;

if (i == k – 1) {

for (int j = 0; j < k; j++) printf("%d ", comb[j]); printf("\n");

} else { i++; comb[i] = comb[i – 1]; }

} else i–;

}

}

2012-09-28 at 20:26

sorry, i must be dumb. the math is beyond me. i’m trying to calculate the possible combinations of 6 numbers. in 2 digit, 3 digit, 4 digit and 5 digit combinations. order doesnt matter so 123, 132, and 321 would all be considered the same combination and not different combinations. mshawobx@hotmail.com

2012-09-28 at 20:28

i came up with 7 5 digit combos, 15 4 digit, 20 3 digit, and 15 2 digit combinations. add the 1 6 digit and 6 1 digits for a total of 64 possible combinations of 6 digits. does this sound correct?

2013-02-19 at 20:52

please, can someone help me with all the possible combinations of five numbers from 1 to 90. numbers are non-repeating !

here is my email: nasibec@gmail.com.

ie n = 90, k = 5.

[1,2,3,….90]= n

2013-03-29 at 22:24

90X89X87X86X85

2013-07-12 at 21:46

My sister recommended I might this way website. He had been completely perfect. This particular distribute essentially built my own day time. You cannot envision basically the way a ton time frame I had expended with this data! Many thanks!

2013-07-21 at 19:42

If you want to get much from this piece of writing

then you have to apply these techniques to your won weblog.

2013-08-03 at 12:51

I’ve been surfing online greater than 3 hours as of late, yet I never found any fascinating article like yours. It is beautiful value sufficient for me. Personally, if all website owners and bloggers made good content as you did, the net will be much more helpful than ever before.

2014-08-19 at 16:00

Good and useful article. I created MS Excel macro based on the algorithm described here. Works perfectly. Thanks, I did not find this content elsewhere!