9b265feb |
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 |