-
Notifications
You must be signed in to change notification settings - Fork 0
/
unrank.c
167 lines (142 loc) · 4.17 KB
/
unrank.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
// Wee command line tool to unrank combinations
#include <string.h>
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <unistd.h>
#include <gmp.h>
#include "combunrank.h"
static const unsigned int nb_algos =
sizeof(unrank_algo_list) / sizeof(name_algo_pair);
static unrank_algo_t get_algorithm(char name[]) {
for (unsigned int i = 0; i < nb_algos; i++) {
if (strcmp(unrank_algo_list[i].name, name) == 0)
return unrank_algo_list[i].func;
}
return NULL;
}
static void print_combination(const int* comb, const int k) {
for (int i = 0; i < k - 1; i++) {
printf("%d, ", comb[i]);
}
if (k > 0) printf("%d", comb[k - 1]);
printf("\n");
}
// ---
// CLI parsing
// ---
typedef struct {
int n;
int k;
mpz_t rank;
char* algo;
} cli_options;
static int usage(char progname[]) {
fprintf(stderr, "usage: %s -n N -k K [-r RANK] [-a ALGORITHM]\n", progname);
fprintf(stderr, "unrank the (N, K)-combination number RANK in lexicographic order\n");
fprintf(stderr, " -r RANK the rank of the combination, if set to -1 unrank all\n"
" combination in lexicographic order (defaults to -1)\n");
fprintf(stderr, " -a ALGORITHM the unranking algorithm to be used, possible values are:\n"
" ");
for (unsigned int i = 0; i < nb_algos - 1; i++) {
fprintf(stderr, "%s,", unrank_algo_list[i].name);
if (i % 3 == 2) fprintf(stderr, "\n ");
else fprintf(stderr, " ");
}
fprintf(stderr, "%s\n", unrank_algo_list[nb_algos - 1].name);
return 1;
}
static int parse_pos_int(char varname, char* s) {
char* endptr;
long res = strtol(s, &endptr, 10);
if (endptr == s)
return -1;
else if (res > INT_MAX) {
fprintf(stderr, "error: %c is too big (> %d).\n", varname, INT_MAX);
return -1;
} else if (res <= 0) {
fprintf(stderr, "error: %c must be positive (got %d).\n", varname, (int)res);
return -1;
} else
return (int)res;
}
static cli_options cli_parse(int argc, char* argv[]) {
cli_options opts;
mpz_init_set_si(opts.rank, -1);
opts.n = -1;
opts.k = -1;
opts.algo = "recursive_method";
int c;
while ((c = getopt(argc, argv, "n:k:r:a:")) != -1) {
switch (c) {
case 'n':
opts.n = parse_pos_int('n', optarg);
break;
case 'k':
opts.k = parse_pos_int('k', optarg);
break;
case 'r':
if (mpz_set_str(opts.rank, optarg, 10) == -1) {
fprintf(stderr, "error: invalid integer %s\n", optarg);
exit(usage(argv[0]));
}
break;
case 'a':
opts.algo = optarg;
break;
default:
abort();
}
}
if (opts.n == -1) {
fprintf(stderr, "error: -n is missing\n");
exit(usage(argv[0]));
}
if (opts.k == -1) {
fprintf(stderr, "error: -k is missing\n");
exit(usage(argv[0]));
}
return opts;
}
int main(int argc, char* argv[]) {
cli_options opts = cli_parse(argc, argv);
// Sanity checks
if (opts.k > opts.n) {
fprintf(stderr, "error: k too big, should be at most n\n");
return usage(argv[0]);
}
mpz_t binom;
mpz_init(binom);
mpz_bin_uiui(binom, opts.n, opts.k);
if (mpz_cmp_si(opts.rank, -1) < 0 || mpz_cmp(opts.rank, binom) >= 0) {
fprintf(stderr, "error: invalid rank, should be in [0; binomial(n, k)]\n");
fprintf(stderr, " got: ");
mpz_out_str(stderr, 10, opts.rank);
fprintf(stderr, "\n binomial(%d, %d) is ", opts.n, opts.k);
mpz_out_str(stderr, 10, binom);
fprintf(stderr, "\n");
return usage(argv[0]);
}
// Select the algorithm
unrank_algo_t algo = get_algorithm(opts.algo);
if (algo == NULL) {
fprintf(stderr, "error: unknown algorithm %s\n", opts.algo);
return usage(argv[0]);
}
int* comb = calloc(opts.k, sizeof(int));
if (mpz_cmp_si(opts.rank, -1) == 0) {
mpz_set_si(opts.rank, 0);
while (mpz_cmp(opts.rank, binom) < 0) {
algo(comb, opts.n, opts.k, opts.rank);
print_combination(comb, opts.k);
mpz_add_ui(opts.rank, opts.rank, 1);
}
} else {
algo(comb, opts.n, opts.k, opts.rank);
print_combination(comb, opts.k);
}
free(comb);
mpz_clear(opts.rank);
mpz_clear(binom);
return 0;
}