75 lines
2 KiB
Rust
75 lines
2 KiB
Rust
use std::env;
|
|
use std::str::FromStr;
|
|
|
|
fn add(list: &mut Vec<usize>, t: usize) {
|
|
list.push(1 | t << 1);
|
|
}
|
|
|
|
fn show(mut t: usize, mut len: usize) {
|
|
while len > 0 {
|
|
len -= 1;
|
|
print!("{}", if (t & 1) != 0 { '(' } else { ')' });
|
|
t >>= 1;
|
|
}
|
|
}
|
|
|
|
fn list_trees(list: &Vec<usize>, offset: &Vec<usize>, n: usize) {
|
|
for i in offset[n]..offset[n+1] {
|
|
show(list[i], n*2);
|
|
println!();
|
|
}
|
|
}
|
|
|
|
/* assemble tree from subtrees
|
|
n: length of tree we want to make
|
|
t: assembled parts so far
|
|
sl: length of subtree we are looking at
|
|
pos: offset of subtree we are looking at
|
|
rem: remaining length to be put together
|
|
*/
|
|
fn assemble(list: &mut Vec<usize>, offset: &mut Vec<usize>, n: usize, t: usize, mut sl: usize, mut pos: usize, rem: usize) {
|
|
if rem == 0 {
|
|
add(list, t);
|
|
return;
|
|
}
|
|
if sl > rem { // need smaller sub-trees
|
|
sl = rem;
|
|
pos = offset[sl];
|
|
} else if pos >= offset[sl+1] {
|
|
// used up sl-trees, try smaller ones
|
|
sl -= 1;
|
|
if sl == 0 {
|
|
return;
|
|
}
|
|
pos = offset[sl];
|
|
}
|
|
assemble(list, offset, n, (t << (2*sl)) | list[pos], sl, pos, rem-sl);
|
|
assemble(list, offset, n, t, sl, pos+1, rem);
|
|
}
|
|
|
|
fn mktrees(list: &mut Vec<usize>, offset: &mut Vec<usize>, n: usize) {
|
|
if offset[n+1] > 0 {
|
|
return;
|
|
}
|
|
if n > 0 {
|
|
mktrees(list, offset, n - 1);
|
|
}
|
|
assemble(list, offset, n, 0, n-1, offset[n-1], n-1);
|
|
offset[n+1] = list.len();
|
|
}
|
|
|
|
fn main() {
|
|
let list: &mut Vec<usize> = &mut vec![];
|
|
let offset: &mut Vec<usize> = &mut vec![0_usize; 32];
|
|
offset[1] = 1_usize;
|
|
let mut n = 5;
|
|
let args: Vec<String> = env::args().collect();
|
|
if args.len() == 2 {
|
|
n = usize::from_str(args[1].as_str()).unwrap_or(5);
|
|
n = if n <= 0 || n > 19 { 5 } else { n };
|
|
}
|
|
add(list, 0);
|
|
mktrees(list, offset, n);
|
|
println!("Number of {}-trees: {}", n, offset[n+1]-offset[n]);
|
|
list_trees(list, offset, n);
|
|
}
|