| 1 | #include <assert.h> |
| 2 | #include <string.h> |
| 3 | |
| 4 | #include "puzzles.h" |
| 5 | |
| 6 | /* horrific and doesn't check overflow. */ |
| 7 | static long factx(long x, long y) |
| 8 | { |
| 9 | long acc = 1, i; |
| 10 | |
| 11 | for (i = y; i <= x; i++) |
| 12 | acc *= i; |
| 13 | return acc; |
| 14 | } |
| 15 | |
| 16 | void reset_combi(combi_ctx *combi) |
| 17 | { |
| 18 | int i; |
| 19 | combi->nleft = combi->total; |
| 20 | for (i = 0; i < combi->r; i++) |
| 21 | combi->a[i] = i; |
| 22 | } |
| 23 | |
| 24 | combi_ctx *new_combi(int r, int n) |
| 25 | { |
| 26 | long nfr, nrf; |
| 27 | combi_ctx *combi; |
| 28 | |
| 29 | assert(r <= n); |
| 30 | assert(n >= 1); |
| 31 | |
| 32 | combi = snew(combi_ctx); |
| 33 | memset(combi, 0, sizeof(combi_ctx)); |
| 34 | combi->r = r; |
| 35 | combi->n = n; |
| 36 | |
| 37 | combi->a = snewn(r, int); |
| 38 | memset(combi->a, 0, r * sizeof(int)); |
| 39 | |
| 40 | nfr = factx(n, r+1); |
| 41 | nrf = factx(n-r, 1); |
| 42 | combi->total = (int)(nfr / nrf); |
| 43 | |
| 44 | reset_combi(combi); |
| 45 | return combi; |
| 46 | } |
| 47 | |
| 48 | /* returns NULL when we're done otherwise returns input. */ |
| 49 | combi_ctx *next_combi(combi_ctx *combi) |
| 50 | { |
| 51 | int i = combi->r - 1, j; |
| 52 | |
| 53 | if (combi->nleft == combi->total) |
| 54 | goto done; |
| 55 | else if (combi->nleft <= 0) |
| 56 | return NULL; |
| 57 | |
| 58 | while (combi->a[i] == combi->n - combi->r + i) |
| 59 | i--; |
| 60 | combi->a[i] += 1; |
| 61 | for (j = i+1; j < combi->r; j++) |
| 62 | combi->a[j] = combi->a[i] + j - i; |
| 63 | |
| 64 | done: |
| 65 | combi->nleft--; |
| 66 | return combi; |
| 67 | } |
| 68 | |
| 69 | void free_combi(combi_ctx *combi) |
| 70 | { |
| 71 | sfree(combi->a); |
| 72 | sfree(combi); |
| 73 | } |
| 74 | |
| 75 | /* compile this with: |
| 76 | * gcc -o combi.exe -DSTANDALONE_COMBI_TEST combi.c malloc.c |
| 77 | */ |
| 78 | #ifdef STANDALONE_COMBI_TEST |
| 79 | |
| 80 | #include <stdio.h> |
| 81 | |
| 82 | void fatal(char *fmt, ...) |
| 83 | { |
| 84 | abort(); |
| 85 | } |
| 86 | |
| 87 | int main(int argc, char *argv[]) |
| 88 | { |
| 89 | combi_ctx *c; |
| 90 | int i, r, n; |
| 91 | |
| 92 | if (argc < 3) { |
| 93 | fprintf(stderr, "Usage: combi R N\n"); |
| 94 | exit(1); |
| 95 | } |
| 96 | |
| 97 | r = atoi(argv[1]); n = atoi(argv[2]); |
| 98 | c = new_combi(r, n); |
| 99 | printf("combi %d of %d, %d elements.\n", c->r, c->n, c->total); |
| 100 | |
| 101 | while (next_combi(c)) { |
| 102 | for (i = 0; i < c->r; i++) { |
| 103 | printf("%d ", c->a[i]); |
| 104 | } |
| 105 | printf("\n"); |
| 106 | } |
| 107 | free_combi(c); |
| 108 | } |
| 109 | |
| 110 | #endif |