diff options
Diffstat (limited to 'apps/plugins/puzzles/src/combi.c')
-rw-r--r-- | apps/plugins/puzzles/src/combi.c | 110 |
1 files changed, 110 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/combi.c b/apps/plugins/puzzles/src/combi.c new file mode 100644 index 0000000000..4c5d1077aa --- /dev/null +++ b/apps/plugins/puzzles/src/combi.c | |||
@@ -0,0 +1,110 @@ | |||
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 | ||