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.