diff options
| -rw-r--r-- | .gitignore | 2 | ||||
| -rw-r--r-- | Makefile | 3 | ||||
| -rw-r--r-- | README.txt | 2 | ||||
| -rw-r--r-- | alg_c.c | 79 | ||||
| -rw-r--r-- | alg_l.c | 41 | ||||
| -rw-r--r-- | alg_r.c | 65 | ||||
| -rw-r--r-- | alg_t.c | 61 |
7 files changed, 253 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..b4b5bec --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +alg_* +!*.c diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..d903d0a --- /dev/null +++ b/Makefile @@ -0,0 +1,3 @@ +all: alg_l alg_t alg_r alg_c + +%: %.c diff --git a/README.txt b/README.txt new file mode 100644 index 0000000..2f6ea8a --- /dev/null +++ b/README.txt @@ -0,0 +1,2 @@ +C implementations of algorithms from Knuth's TAOCP "Generating All +Combinations" chapter. @@ -0,0 +1,79 @@ +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> + +#define MAX(A, B) (((A) > (B)) ? (A) : (B)) + +int main(int argv, char **argc) { + if (argv < 3) { + assert(argv > 0); + printf("Usage: %s [n] [t]\n", argc[0]); + return -1; + } + + long n = atoi(argc[1]), + t = atoi(argc[2]), + s = n - t; + + assert(1 < t && t < n); + + char *a = calloc(n, sizeof(*a)), + *w = calloc(n + 1, sizeof(*a)); + +C1_initialize: + for (size_t j = 0; j < s; j++) + a[j] = 0; + for (size_t j = s; j < n; j++) + a[j] = 1; + for (size_t j = 0; j <= n; j++) + w[j] = 1; + size_t r = (s > 0) ? s : t; + +C2_visit: + for (size_t k = n; k --> 0;) + printf("%lu", a[k]); + printf("\n"); + +C3_find_j_and_branch: + size_t j = r; + while (w[j] == 0) { + w[j] = 1; + j = j + 1; + } + if (j == n) return 0; + w[j] = 0; + if (j % 2 == 1 && a[j] != 0) goto C4_move_right_one; + if (j % 2 == 0 && a[j] != 0) goto C5_move_right_two; + if (j % 2 == 0 && a[j] == 0) goto C6_move_left_one; + if (j % 2 == 1 && a[j] == 0) goto C7_move_left_two; + +C4_move_right_one: + a[j - 1] = 1; + a[j] = 0; + if (r == j && j > 1) r = j - 1; + else if (r == j - 1) r = j; + goto C2_visit; + +C5_move_right_two: + if (a[j - 2] != 0) goto C4_move_right_one; + a[j - 2] = 1; + a[j] = 0; + if (r == j) r = MAX(j - 2, 1); + else if (r == j - 2) r = j - 1; + goto C2_visit; + +C6_move_left_one: + a[j] = 1; + a[j - 1] = 0; + if (r == j && j > 1) r = j - 1; + else if (r == j - 1) r = j; + goto C2_visit; + +C7_move_left_two: + if (a[j - 1] != 0) goto C6_move_left_one; + a[j] = 1; + a[j - 2] = 0; + if (r == j - 2) r = j; + else if (r == j - 1) r = j - 2; + goto C2_visit; +} @@ -0,0 +1,41 @@ +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> + +int main(int argv, char **argc) { + if (argv < 3) { + assert(argv > 0); + printf("Usage: %s [n] [t]\n", argc[0]); + return -1; + } + + size_t n = atoi(argc[1]), + t = atoi(argc[2]); + + size_t *c = calloc(t + 3, sizeof(*c)); + +L1_initialize: + for (size_t j = 1; j <= t; j++) + c[j] = j - 1; + c[t + 1] = n; + c[t + 2] = 0; + +L2_visit: + for (size_t j = t; j >= 1; j--) + printf("%lu ", c[j]); + printf("\n"); + +L3_find_j: + size_t j = 1; + while (c[j] + 1 == c[j + 1]) { + c[j] = j - 1; + j = j + 1; + } + +L4_maybe_done: + if (j > t) return 0; + +L5_increase_c_j: + c[j] = c[j] + 1; + goto L2_visit; +} @@ -0,0 +1,65 @@ +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> + +int main(int argv, char **argc) { + if (argv < 3) { + assert(argv > 0); + printf("Usage: %s [n] [t]\n", argc[0]); + return -1; + } + + size_t n = atoi(argc[1]), + t = atoi(argc[2]); + + assert(1 < t && t < n); + + size_t *c = calloc(t + 2, sizeof(*c)); + size_t j; + +R1_initialize: + for (size_t j = 1; j <= t; j++) + c[j] = j - 1; + c[t + 1] = n; + +R2_visit: + for (size_t k = t; k >= 1; k--) + printf("%lu ", c[k]); + printf("\n"); + +R3_maybe_easy_case: + if ((t % 2) == 1) { + if (c[1] + 1 < c[2]) { + c[1] = c[1] + 1; + goto R2_visit; + } + j = 2; + goto R4_try_decrease_c_j; + } else { + if (c[1] > 0) { + c[1] = c[1] - 1; + goto R2_visit; + } else { + j = 2; + goto R5_try_increase_c_j; + } + } + +R4_try_decrease_c_j: + if (c[j] >= j) { + c[j] = c[j - 1]; + c[j - 1] = j - 2; + goto R2_visit; + } + j = j + 1; + +R5_try_increase_c_j: + if (c[j] + 1 < c[j + 1]) { + c[j - 1] = c[j]; + c[j] = c[j] + 1; + goto R2_visit; + } else { + j = j + 1; + if (j <= t) goto R4_try_decrease_c_j; + } +} @@ -0,0 +1,61 @@ +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> + +int main(int argv, char **argc) { + if (argv < 3) { + assert(argv > 0); + printf("Usage: %s [n] [t]\n", argc[0]); + return -1; + } + + size_t n = atoi(argc[1]), + t = atoi(argc[2]); + + assert(t < n); + + size_t *c = calloc(t + 3, sizeof(*c)); + +T1_initialize: + for (size_t j = 1; j <= t; j++) + c[j] = j - 1; + c[t + 1] = n; + c[t + 2] = 0; + + size_t j = t; + +T2_visit: + for (size_t k = t; k >= 1; k--) + printf("%lu ", c[k]); + printf("\n"); + + size_t x; + if (j > 0) { + x = j; + goto T6_increase_c_j; + } + +T3_maybe_easy_case: + if (c[1] + 1 < c[2]) { + c[1] = c[1] + 1; + goto T2_visit; + } else { + j = 2; + } + +T4_find_j: + c[j - 1] = j - 2; + x = c[j] + 1; + if (x == c[j + 1]) { + j = j + 1; + goto T4_find_j; + } + +T5_maybe_done: + if (j > t) return 0; + +T6_increase_c_j: + c[j] = x; + j = j - 1; + goto T2_visit; +} |