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 (c0, c1, ..., cn), start from the back and for ci, if it is larger than n - k + 1 + i then increment it and go on to the next indice i. After this, if c0 > n - k, then this is not a valid combination so we stop. Otherwise give ci+1, ci+2, ... the values of ci + 1, ci+1 + 1, .... Jump to 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!
2015-08-15 at 14:44
nice info mas , Afric
2017-08-30 at 13:55
Wow, wonderful weblog structure! How lengthy have you ever been running a blog for? you make running a blog look easy. The entire look of your website is excellent, let alone the content!
2017-11-22 at 22:51
attorney Marketing
Generating Combinations: 1 | Computer programming
2017-12-18 at 21:01
Lovely just what I was searching for. Thanks to the author for taking his clock time on this
one.
2019-04-30 at 20:03
[…] une meilleure explication Ah, si vous essayez de modifier le programme que vous avez trouvé sur compprog.wordpress.com/2007/10/17/generating-combinations-1 pour mettre le résultat dans un tableau au lieu de la sortie standard stdout? C'est le droit.Et […]
2019-09-19 at 1:51
I used to be recommended this web site by my cousin. I am not positive whether or not this publish is written through him as nobody else know such designated approximately my difficulty. You’re incredible! Thank you!|
2020-10-25 at 3:39
gaynor
Generating Combinations: 1 | Computer programming