next up previous contents index Search
Next: 0.5.3.2 References Up: 0.5.3 Combinations Previous: 0.5.3 Combinations

0.5.3.1 Source Code

int *r, n, k;

int main (void) {
  printf(``Please enter n and k (0 < k <= n): ``);
  scanf(``%d %d'', &n, &k);
  r = (int *) malloc(k+1 * sizeof(int));
  r[0] = 0;
  combin(1);
}

void combin (int m) {
  int i;

  if (m <= k) {
    for (r[m] = r[m-1] + 1; r[m] <= n-k-m; r[m]++)
      combin(m + 1);
  } else {
    for (i = 1; i <= k; i++)
      printf(``%d ``, r[i]);
    printf(``\n'');
  }
}

Here is a non-recursive implementation written by Jock Cooper that, given the number of items and the number of items in a set, computes the sets.



/* -- combin.c -- */



#include 
 #include 
 
 int increment(int numcnt, int setcnt, int counter[]);
 int addup(int setcnt, int counter[]);
 int initcounter(int setcnt, int counter[]);
 int combinations(int numcnt, int setcnt, int items[], int counter[], int results[]);
 
 main(int c,char *v[])
 {
   int numitems, numcomb;
   int *array, *results;
   int *counter;
   int idx;
      
   if (c != 3)
   {
     fprintf(stderr,"usage: %s numitems numcomb\n", v[0]);
     exit(1);
   }
   numitems= atoi(v[1]);
   numcomb = atoi(v[2]);
      
   array = calloc(numitems, sizeof(int));
   counter = calloc(numcomb, sizeof(int));
   results = calloc(numcomb, sizeof(int));
      
   for (idx=0; idx< numitems; ++idx)
   {
     array[idx] = rand() % 5000;
     printf("%d ", array[idx]);
   }
   printf("\n");
   initcounter(numcomb, counter);
   while (combinations(numitems, numcomb, array, counter, results))
   {
     for (idx=0; idx numcnt)
     {
       overflow=1;
        
       digit2=digit;
       --digit;
       if (digit <0) 
       {
         return 0;
       }
 
       while (digit2 < setcnt) counter[digit2++]=1;
     }
     else
     {
       overflow=0;
     }
   }
   while (overflow==1);
   return 1;
 }
 
 
 int addup(int setcnt, int counter[])
 {
   int result=0;
   int idx;
      
   for (idx=0; idx




Scott Gasch
1999-07-09