OFFSET
0,2
LINKS
A. Karttunen, Alternative Catalan Orderings (with the complete Scheme source)
EXAMPLE
The rooted plane trees encoded here are:
.....................o........o.........o......o...o...
.....................|........|.........|.......\./....
.......o....o...o....o....o...o..o.o.o..o...o....o.....
.......|.....\./.....|.....\./....\|/....\./.....|.....
(AT)......(AT)......(AT)......(AT)......(AT)......(AT)......(AT)......(AT).....
0......1......2......3......4......5......6......7.....
Note that we recurse on the run length - 1, thus for 4 = 100 in binary, we construct a tree by joining trees 0 (= 1-1) and 1 (= 2-1) respectively from left to right. For 5 (101) we construct a tree by joining three copies of tree 0 (a single leaf) with a new root node. For 6 (110) we join trees 1 and 0 to get a mirror image of tree 4. For 7 (111) we just add a new root node below tree 2.
PROG
(Scheme functions showing the essential idea. For the complete source, follow the "Alternative Catalan Orderings" link:)
(define (binruns->parenthesization n) (map binruns->parenthesization (map -1+ (binexp->runcount1list n))))
(define (binexp->runcount1list n) (if (zero? n) (list) (let loop ((n n) (rc (list)) (count 0) (prev-bit (modulo n 2))) (if (zero? n) (cons count rc) (if (eq? (modulo n 2) prev-bit) (loop (floor->exact (/ n 2)) rc (1+ count) (modulo n 2)) (loop (floor->exact (/ n 2)) (cons count rc) 1 (modulo n 2)))))))
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Antti Karttunen, Sep 13 2002
STATUS
approved