-
Notifications
You must be signed in to change notification settings - Fork 1
/
CombinatorialEnumerations.java
219 lines (176 loc) · 5.63 KB
/
CombinatorialEnumerations.java
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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
package Combinatorics;
import java.util.Arrays;
//Enumeration of Cominatorial Sequences. Universal Method in 0(n^2)
public class CombinatorialEnumerations {
// subclass and implement count() method
public static abstract class AbstractEnumeration {
// range of definition of sequence elements
protected final int range;
// length of generated sequences
protected final int length;
protected AbstractEnumeration(int range, int length) {
this.range = range;
this.length = length;
}
// returns number of combinatorial sequences starting with prefix
// by contract only the last element of prefix can be invalid and in this case 0 must be returned
protected abstract long count(int[] prefix);
public int[] next(int[] sequence) {
return fromNumber(toNumber(sequence) + 1);
}
public long totalCount() {
return count(new int[0]);
}
public long toNumber(int[] sequence) {
long res = 0;
for (int i = 0; i < sequence.length; i++) {
int[] prefix = Arrays.copyOf(sequence, i + 1);
for (prefix[i] = 0; prefix[i] < sequence[i]; ++prefix[i]) {
res += count(prefix);
}
}
return res;
}
public int[] fromNumber(long number) {
int[] sequence = new int[length];
for (int i = 0; i < sequence.length; i++) {
int[] prefix = Arrays.copyOf(sequence, i + 1);
for (prefix[i] = 0; prefix[i] < range; ++prefix[i]) {
long cur = count(prefix);
if (number < cur) {
break;
}
number -= cur;
}
sequence[i] = prefix[i];
}
return sequence;
}
public void enumerate() {
System.out.println(getClass().getName());
long total = totalCount();
for (long i = 0; i < total; i++) {
int[] p = fromNumber(i);
System.out.println(i + " " + Arrays.toString(p));
long j = toNumber(p);
if (i != j)
throw new RuntimeException();
}
}
}
public static class Arrangements extends AbstractEnumeration {
public Arrangements(int n, int k) {
super(n, k);
}
@Override
protected long count(int[] prefix) {
int size = prefix.length;
// if the last element appears twice, then prefix is invalid and 0 must be returned
for (int i = 0; i < size - 1; i++)
if (prefix[size - 1] == prefix[i])
return 0;
long res = 1;
for (int i = 0; i < length - size; i++)
res *= range - size - i;
return res;
}
}
public static class Permutations extends Arrangements {
public Permutations(int n) {
super(n, n);
}
}
public static class Combinations extends AbstractEnumeration {
final long[][] binomial;
public Combinations(int n, int k) {
super(n, k);
binomial = new long[n + 1][n + 1];
// calculate binomial coefficients in advance
for (int i = 0; i <= n; i++)
for (int j = 0; j <= i; j++)
binomial[i][j] = (j == 0) ? 1 : binomial[i - 1][j - 1] + binomial[i - 1][j];
}
@Override
protected long count(int[] prefix) {
int size = prefix.length;
// if there is no combination with given prefix, 0 must be returned.
// by contract only the last element can make prefix invalid.
if (size >= 2 && prefix[size - 1] <= prefix[size - 2])
return 0;
// prefix is valid. return the number of combinations starting with prefix
int last = size > 0 ? prefix[size - 1] : -1;
return binomial[range - 1 - last][length - size];
}
}
public static class CorrectBracketSequences extends AbstractEnumeration {
final long[][] d;
// sequenceLength must be a multiple of 2
public CorrectBracketSequences(int sequenceLength) {
super(2, sequenceLength);
d = new long[sequenceLength + 1][sequenceLength / 2 + 1];
// d[i][j] - number of bracket sequences of length i with balance j
d[0][0] = 1;
for (int i = 1; i <= sequenceLength; i++) {
for (int balance = 0; balance <= sequenceLength / 2; balance++) {
if (balance - 1 >= 0)
d[i][balance] += d[i - 1][balance - 1];
if (balance + 1 <= sequenceLength / 2)
d[i][balance] += d[i - 1][balance + 1];
}
}
}
@Override
protected long count(int[] prefix) {
int size = prefix.length;
int balance = 0;
for (int cur : prefix)
// 0 designates '('
// 1 designates ')'
balance += cur == 0 ? 1 : -1;
if (balance < 0 || balance > length - size)
return 0;
return d[length - size][balance];
}
}
public static class Partitions extends AbstractEnumeration {
final long[][] pp;
public Partitions(int value) {
super(value + 1, value);
long[][] p = new long[value + 1][value + 1];
// p[i][j] - number of partitions of i with largest summand equal to j
p[0][0] = 1;
for (int i = 1; i <= value; i++)
for (int j = 1; j <= i; j++)
p[i][j] = p[i - 1][j - 1] + p[i - j][j];
pp = new long[value + 1][value + 1];
for (int i = 1; i <= value; i++)
for (int j = 1; j <= value; j++)
pp[i][j] = p[i][j] + pp[i][j - 1];
}
@Override
protected long count(int[] prefix) {
int size = prefix.length;
int sum = 0;
for (int e : prefix)
sum += e;
if (sum == range - 1)
return 1;
if (sum > range - 1 || size > 0 && prefix[size - 1] == 0 || size >= 2 && prefix[size - 1] > prefix[size - 2])
return 0;
int last = size > 0 ? prefix[size - 1] : range - 1;
return pp[range - 1 - sum][last];
}
}
public static void main(String[] args) {
Permutations permutations = new Permutations(3);
permutations.enumerate();
Combinations combinations = new Combinations(4, 3);
combinations.enumerate();
Arrangements arrangements = new Arrangements(3, 2);
arrangements.enumerate();
CorrectBracketSequences correctBracketSequences = new CorrectBracketSequences(6);
correctBracketSequences.enumerate();
Partitions partitions = new Partitions(4);
partitions.enumerate();
}
}