92 lines
2.2 KiB
Java
92 lines
2.2 KiB
Java
import java.util.ArrayList;
|
|
import java.util.List;
|
|
|
|
public class ListRootedTrees {
|
|
private static final List<Long> TREE_LIST = new ArrayList<>();
|
|
|
|
private static final List<Integer> OFFSET = new ArrayList<>();
|
|
|
|
static {
|
|
for (int i = 0; i < 32; i++) {
|
|
if (i == 1) {
|
|
OFFSET.add(1);
|
|
} else {
|
|
OFFSET.add(0);
|
|
}
|
|
}
|
|
}
|
|
|
|
private static void append(long t) {
|
|
TREE_LIST.add(1 | (t << 1));
|
|
}
|
|
|
|
private static void show(long t, int l) {
|
|
while (l-- > 0) {
|
|
if (t % 2 == 1) {
|
|
System.out.print('(');
|
|
} else {
|
|
System.out.print(')');
|
|
}
|
|
t = t >> 1;
|
|
}
|
|
}
|
|
|
|
private static void listTrees(int n) {
|
|
for (int i = OFFSET.get(n); i < OFFSET.get(n + 1); i++) {
|
|
show(TREE_LIST.get(i), n * 2);
|
|
System.out.println();
|
|
}
|
|
}
|
|
|
|
private static void assemble(int n, long t, int sl, int pos, int rem) {
|
|
if (rem == 0) {
|
|
append(t);
|
|
return;
|
|
}
|
|
|
|
var pp = pos;
|
|
var ss = sl;
|
|
|
|
if (sl > rem) {
|
|
ss = rem;
|
|
pp = OFFSET.get(ss);
|
|
} else if (pp >= OFFSET.get(ss + 1)) {
|
|
ss--;
|
|
if (ss == 0) {
|
|
return;
|
|
}
|
|
pp = OFFSET.get(ss);
|
|
}
|
|
|
|
assemble(n, t << (2 * ss) | TREE_LIST.get(pp), ss, pp, rem - ss);
|
|
assemble(n, t, ss, pp + 1, rem);
|
|
}
|
|
|
|
private static void makeTrees(int n) {
|
|
if (OFFSET.get(n + 1) != 0) {
|
|
return;
|
|
}
|
|
if (n > 0) {
|
|
makeTrees(n - 1);
|
|
}
|
|
assemble(n, 0, n - 1, OFFSET.get(n - 1), n - 1);
|
|
OFFSET.set(n + 1, TREE_LIST.size());
|
|
}
|
|
|
|
private static void test(int n) {
|
|
if (n < 1 || n > 12) {
|
|
throw new IllegalArgumentException("Argument must be between 1 and 12");
|
|
}
|
|
|
|
append(0);
|
|
|
|
makeTrees(n);
|
|
System.out.printf("Number of %d-trees: %d\n", n, OFFSET.get(n + 1) - OFFSET.get(n));
|
|
listTrees(n);
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
test(5);
|
|
}
|
|
}
|