1  
   2  #include <stdio.h>
   3  
   4  /* Prints out a combination like {1, 2} */
   5  void printc(int comb[], int k) {
   6  	printf("{");
   7  	int i;
   8  	for (i = 0; i < k; ++i)
   9  		printf("%d, ", comb[i] + 1);
  10  	printf("\b\b}\n");
  11  }
  12  
  13  /*
  14  	next_comb(int comb[], int k, int n)
  15  		Generates the next combination of n elements as k after comb
  16  
  17  	comb => the previous combination ( use (0, 1, 2, ..., k) for first)
  18  	k => the size of the subsets to generate
  19  	n => the size of the original set
  20  
  21  	Returns: 1 if a valid combination was found
  22  		0, otherwise
  23  */
  24  int next_comb(int comb[], int k, int n) {
  25  	int i = k - 1;
  26  	++comb[i];
  27  	while ((i >= 0) && (comb[i] >= n - k + 1 + i)) {
  28  		--i;
  29  		++comb[i];
  30  	}
  31  
  32  	if (comb[0] > n - k) /* Combination (n-k, n-k+1, ..., n) reached */
  33  		return 0; /* No more combinations can be generated */
  34  
  35  	/* comb now looks like (..., x, n, n, n, ..., n).
  36  	Turn it into (..., x, x + 1, x + 2, ...) */
  37  	for (i = i + 1; i < k; ++i)
  38  		comb[i] = comb[i - 1] + 1;
  39  
  40  	return 1;
  41  }
  42  
  43  int main(int argc, char *argv[]) {
  44  	int n = 5; /* The size of the set; for {1, 2, 3, 4} it's 4 */
  45  	int k = 3; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
  46  	int comb[16]; /* comb[i] is the index of the i-th element in the
  47  			combination */
  48  
  49  	/* Setup comb for the initial combination */
  50  	int i;
  51  	for (i = 0; i < k; ++i)
  52  		comb[i] = i;
  53  
  54  	/* Print the first combination */
  55  	printc(comb, k);
  56  
  57  	/* Generate and print all the other combinations */
  58  	while (next_comb(comb, k, n))
  59  		printc(comb, k);
  60  
  61  	return 0;
  62  }
  63