algorithm for generating number combinations without repetition

Question

I checked almost every similar post in here but I couldn't figure out how I can do what I want. What I am trying is to give an input in a C program, let say number 4, and the program return the following numbers in an array:

1
2
3
4
12
13
14
23
24
34
123
134
124
1234

To be more clear: If the input number is 4 then i want to use digits 1-4 and generate all the possible combinations of digits(from 1-digit combinations to 4-digit combinations) without digit repetitions.

I tried the following code:

#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");
}


    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;
}

The above program prints the result. I want to get the result somehow.. but I can't because the above code prints the result in a strange manner.

Answer 1

A comment in the accepted answer asks:

"Great short solution, is there a way to change it such that it generates the combinations in order? Such as 1,2,3,4,12,13,23,14,24,34,123,124,134,234,1234"

The following program will produce the combinations in that order.

This program works the same way as the accepted answer -- using a number's underlying binary pattern to find the combinations.

First the program displays C(4,0), then C(4,1), followed by C(4,2), C(4,3) and finally C(4,4).

The program can easily be extended. Just increase the value of n and add the appropriate powers of 2 to the array. While not very efficient the program does produce the requested sequence of combinations.

/* Combin.c -- display the combinations of n objects

   to omit the empty set, C(n,0), change the start value in the for loop in
   the main function from 0 to 1
*/

#include <stdio.h>

int numOfSetBits(int num)
{
    int count = 0;

    while (num > 0) {
        if ((num & 1) == 1) {
            ++count;
        }        
        num /= 2;
    }

    return count;
}

void displayComb(int n, int r)
{
    int power2[] = { 1, 2, 4, 8, 16 };

    for (int i = 0; i < power2[n]; ++i) {
        if (numOfSetBits(i) == r) {
            printf(" {");
            for (int j = 0; j < n; ++j) {
                if (i & power2[j]) {
                    putchar((j + 1) + '0');
                }
            }
            putchar('}');
        }
    }    
}

int main (void)
{
    putchar('\n');

    int n = 4;
    for (int i = 0; i <= n; ++i) {
        printf("C(%d,%d) =", n, i);
        displayComb(n, i);
        putchar('\n');
    }

    return 0;
}

program output:

C(4,0) = {}
C(4,1) = {1} {2} {3} {4}
C(4,2) = {12} {13} {23} {14} {24} {34}
C(4,3) = {123} {124} {134} {234}
C(4,4) = {1234}

Answer 2

Here is a program that generates combinations of numbers. It is written in C. But it could be rewritten in any other language. For now, just compile it and try it !

#include <stdio.h>
#include <stdlib.h>
int v[100], stack[100];
int sp,i,n,g;
int main()
{
printf("Dimension of V:");
scanf( "%d",&n);
//Input numbers
for (i=0 ; i<n ; i++) {
printf("V[%d]=",i);
scanf( "%d",&g);
v[i]=g;
}
printf("running...\n");
sp=-1;
while(1) {
// stack ones until stack overflow
    while(sp<n-1)  {
      sp=sp+1;
      stack[sp]=1;
      for (i=0 ; i<=sp ; i++) if (stack[i]==1) printf("v[%d]=%d ",i,v[i]);
      printf("\n");
   }
// unstack all the zeros until top of stack is equal one
while (stack[sp]==0 && sp>=0) sp=sp-1;
// if Bottom of stack is reached then stop
if (sp<0) break;
// set top of stack from one to zero
      stack[sp]=0;
  }
return 0;
}

run for n=4 :

[oldache@localhost fin]$ ./comb
Dimension of V:4
V[0]=10
V[1]=20
V[2]=30
V[3]=40
running...
v[0]=10
v[0]=10 v[1]=20
v[0]=10 v[1]=20 v[2]=30
v[0]=10 v[1]=20 v[2]=30 v[3]=40
v[0]=10 v[1]=20 v[3]=40
v[0]=10 v[2]=30
v[0]=10 v[2]=30 v[3]=40
v[0]=10 v[3]=40
v[1]=20
v[1]=20 v[2]=30
v[1]=20 v[2]=30 v[3]=40
v[1]=20 v[3]=40
v[2]=30
v[2]=30 v[3]=40
v[3]=40

Answer 3

We use a int to represent a set. For the i-th bit, if it is 1, then i is in the set and vice versa.

Take a example:1010(2)={4,2} 1111(2)={4,3,2,1}

For every element that will be considered, there is two choices: in or not in the set.

So, there are 2^n different set in total. And in my code, I just enumerate every possible int which is corresponding a set, and output the corresponding set.

So we get this code:

for(int i=1;i<(1<<n);i++)
{
    for(int j=0;j<n;j++)
        if ((1<<j)&i) printf("%d",j+1);
    puts("");
}

when n=4, output:

1
2
12
3
13
23
123
4
14
24
124
34
134
234
1234

If you want to output the answer as the order of giving, just make them string and put these string in vector and sort.

If n is large, you can use bitset. But when n>30,it may not be terminates in hours. So int is efficient.