# 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

### Subscribe to Post, Code and Quiet Time.

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
jamie@example.com
Subscribe