Print all combination of that select n elements from 1,2,3,...,m.

"C" is for "combination". A combination is an un-ordered collection of distinct elements, usually of a prescribed size and taken from a given set.

   C(n, r) = n!/[r!(n-r)!] 

#include <stdio.h>
#include <sys/time.h>

int a[1001];

// selected n numbers stored in array a
// a[1], a[2], ... , a[n]
// a[i+1] > a[i]
// a[i] - i <= m - n + 1

void comos(int n, int m) {
  int i,j;
  if (n > m)
    return;
  for (i = 1; i <= n; i++) {
    a[i] = i;
  }
  int cur = n;
  do {
    if (a[cur]-cur <= m - n) {
      for (i = 1; i <= n; i++)
        printf("%d ", a[i]);
      printf("\n");
      a[cur]++;
      continue;
    } else {
      if (cur == 1) {
        break;
      }
      a[--cur]++;
      for (i = 1; i <= (n-cur); i++)
        a[cur+i] = a[cur] + i;
      if (a[cur] - cur < m - n + 1)
        cur=n;
    }
  } while(1);
}

int main() {
  int N, M;
  while (scanf("%d %d", &N, &M) != EOF) {
    if (N <= M) {
      struct timeval begin, end;
      gettimeofday(&begin, 0);
      comos(N, M);
      gettimeofday(&end, 0);
      printf("print comos(%d, %d) used %ld microseconds\n", N, M, end.tv_usec-begin.tv_usec);
    } else {
      printf("Invalid Input, %d <= %d is false\n", N, M);
    }
  }
  return 0;
}

1 5
1
2
3
4
5
print comos(1, 5) used 116 microseconds
2 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
print comos(2, 5) used 171 microseconds
3 5
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
print comos(3, 5) used 153 microseconds
4 5
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
print comos(4, 5) used 97 microseconds
5 5
1 2 3 4 5
print comos(5, 5) used 33 microseconds

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️