Generating combinations of n elements in groups of k

Question

I've written this program that writes all the combinations (without repetition) of n elements in groups of k.

I think the code is good, but I like to know if you have some better (or faster) solutions.

The elements to combine are always the number from 0 to n-1, the program calls a function (newCombo()) for each generated combination.

EG: Using n=6 and k=4 the program generates the following output:

0 1 2 3 
0 1 2 4 
0 1 2 5 
0 1 3 4 
0 1 3 5 
0 1 4 5 
0 2 3 4 
0 2 3 5 
0 2 4 5 
0 3 4 5 
1 2 3 4 
1 2 3 5 
1 2 4 5 
1 3 4 5 
2 3 4 5 

The code is below:

#include <stdio.h>
void newCombo(int *a,int n,int k);
void newCombo(int *a,int n,int k)
{
 int i;
 for(i=0;i<k;i++)
 printf("%d ",a[i]);
 puts("");
}
int main(int argc,char *argv[])
{
 int a[30];
 int n,k,p;
 do {
 printf("Insert n and k - EG: 5 3: ");
 if (scanf("%d %d",&n,&k)!=2)
 return 1;
 if (k>n)
 puts("k shall be <= n !");
 if (k==0 || n==0)
 puts("k and n shall not be 0!");
 if (k>30)
 puts("k shall be <=30");
 } while (k>n || k==0 || n==0 || k>30);
 p=0;
 a[0]=-1;
 do {
 if (++a[p]>n-k+p) {
 p--;
 } else {
 if (p<k-1) {
 a[p+1]=a[p];
 p++;
 } else {
 newCombo(a,n,k);
 }
 }
 } while(p>=0);
 return 0;
}

Answer 1

Main loop could be simplified a little

There's not too much to say about the current program. It works and it seems like it is using the fastest method possible. It basically adds one to the last array element and moves left when an "overflow" happens. At the end of handling all the "overflows", it moves back to the right, resetting each digit.

The one thing that I would change is basically that when you are moving back to the right, there's no need to use the main loop to do that. It causes extra compares of (p >= 0) which are always going to be true and extra ++a[p] which are unnecessary. You could instead handle moving to the right in its own nested loop. Here's how it would look like:

do {
 if (++a[p]>n-k+p) {
 // Overflow, move to the next element on the left.
 p--;
 continue;
 }
 // Resolve overflows by resetting digits to the right.
 while (p < k-1) {
 a[p+1]=a[p]+1;
 p++;
 }
 newCombo(a,n,k);
} while(p>=0);

An interesting challenge

What if I asked you to write a program that prints out the N'th combination instead of all of them. In your given example with n=6 and k=4, the 0th combination would be 0 1 2 3 and the 14th (and last) combination would be 2 3 4 5. I find this task to be much more difficult (and useful) than generating all combinations.

• Sergio Formiggini: Yes, @JS1, my goal is to solve the challenge you're indicating me!!! A lot of time ago I wrote something like what you say and it's what I'm searching to rebuild! ... In the last years I had no time for these thing. My job was on other things and now, in a period where I'm unemployed, I'm playing with various things, suspended, to maintain my knowledge and to enjoy myself.
• JS1: @SergioFormiggini Ok when you solve that next problem you can post it for review. It's interesting, I was just trying to solve this problem a couple of days ago (the one where you find the Nth combination). I wrote a solution for it several years ago, but I couldn't remember how I did it and couldn't figure out from scratch how to do it until I peeked at my old code. So it definitely isn't a trivial problem and it requires some thought.
• Sergio Formiggini: The only thing I've found (at now) is that if I use a binary value of n bits when I set to 1 the bits at the positions indicated by the values of the elements I've in a combination all number generated have k bits set to 1 and n - k set to 0 (obviously) . An intersting thing is that setting 1 the bit in the position n-ev-1 (where ev is the element value) we obtain a sequence of decreasing numbers ... I think that is an interesting way to solve the challenge. Have you hints about?
• JS1: @SergioFormiggini My hint: How many combinations start with 0 ...? And how many start with 1 ...? That gives you an idea of how to find the first digit.