Working with Dyck words and non-crossing linear chords, I realized that one can also generate all non-crossing partitions of a finite set using Dyck words. I just need a new conversion function.
Consider the finite set \(\[n\] = {0,1,\ldots,n}\) and a partition \(\mathcal{P}\) of \(n\). We call such a partition as non-crossing if the corresponding chord diagram has no crossings.
Let me start with a slightly improved version of the generation of all Dyck words of a specific length:
(defun dyck-words (n &optional (a 0) (acc '(())))
(labels ((insert (xxs ys)
(mapcar (lambda (xs) (append xs ys)) xxs)))
(if (= a n)
(insert acc (loop repeat n collect 1))
(append (dyck-words n (1+ a) (insert acc '(0)))
(if (> a 0) (dyck-words (1- n) (1- a) (insert acc '(1))))))))Next, a new function that converts a Dyck word into a non-crossing partition:
(defun unwind (xs stack &optional res)
(if (or (null xs) (= 0 (car xs)))
(values xs stack res)
(unwind (cdr xs) (cdr stack) (cons (car stack) res))))
(defun convert (xs &optional (pos 0) stack res)
(cond ((null xs) res)
((= 0 (car xs)) (convert (cdr xs) (1+ pos) (cons pos stack) res))
(t (multiple-value-bind
(ys st re) (unwind xs stack)
(convert ys pos st (cons re res))))))
(mapcar #'convert (dyck-words 6))
(((0 1 2 3 4 5)) ((0 1 2 3 5) (4)) ((0 1 2 5) (3 4)) ((0 1 5) (2 3 4))
((0 5) (1 2 3 4)) ((5) (0 1 2 3 4)) ((0 1 2 4 5) (3)) ((0 1 2 5) (4) (3))
((0 1 5) (2 4) (3)) ((0 5) (1 2 4) (3)) ((5) (0 1 2 4) (3)) ((0 1 4 5) (2 3))
((0 1 5) (4) (2 3)) ((0 5) (1 4) (2 3)) ((5) (0 1 4) (2 3)) ((0 4 5) (1 2 3))
((0 5) (4) (1 2 3)) ((5) (0 4) (1 2 3)) ((4 5) (0 1 2 3)) ((5) (4) (0 1 2 3))
((0 1 3 4 5) (2)) ((0 1 3 5) (4) (2)) ((0 1 5) (3 4) (2)) ((0 5) (1 3 4) (2))
((5) (0 1 3 4) (2)) ((0 1 4 5) (3) (2)) ((0 1 5) (4) (3) (2))
((0 5) (1 4) (3) (2)) ((5) (0 1 4) (3) (2)) ((0 4 5) (1 3) (2))
((0 5) (4) (1 3) (2)) ((5) (0 4) (1 3) (2)) ((4 5) (0 1 3) (2))
((5) (4) (0 1 3) (2)) ((0 3 4 5) (1 2)) ((0 3 5) (4) (1 2))
((0 5) (3 4) (1 2)) ((5) (0 3 4) (1 2)) ((0 4 5) (3) (1 2))
((0 5) (4) (3) (1 2)) ((5) (0 4) (3) (1 2)) ((4 5) (0 3) (1 2))
((5) (4) (0 3) (1 2)) ((3 4 5) (0 1 2)) ((3 5) (4) (0 1 2))
((5) (3 4) (0 1 2)) ((4 5) (3) (0 1 2)) ((5) (4) (3) (0 1 2))
((0 2 3 4 5) (1)) ((0 2 3 5) (4) (1)) ((0 2 5) (3 4) (1)) ((0 5) (2 3 4) (1))
((5) (0 2 3 4) (1)) ((0 2 4 5) (3) (1)) ((0 2 5) (4) (3) (1))
((0 5) (2 4) (3) (1)) ((5) (0 2 4) (3) (1)) ((0 4 5) (2 3) (1))
((0 5) (4) (2 3) (1)) ((5) (0 4) (2 3) (1)) ((4 5) (0 2 3) (1))
((5) (4) (0 2 3) (1)) ((0 3 4 5) (2) (1)) ((0 3 5) (4) (2) (1))
((0 5) (3 4) (2) (1)) ((5) (0 3 4) (2) (1)) ((0 4 5) (3) (2) (1))
((0 5) (4) (3) (2) (1)) ((5) (0 4) (3) (2) (1)) ((4 5) (0 3) (2) (1))
((5) (4) (0 3) (2) (1)) ((3 4 5) (0 2) (1)) ((3 5) (4) (0 2) (1))
((5) (3 4) (0 2) (1)) ((4 5) (3) (0 2) (1)) ((5) (4) (3) (0 2) (1))
((2 3 4 5) (0 1)) ((2 3 5) (4) (0 1)) ((2 5) (3 4) (0 1)) ((5) (2 3 4) (0 1))
((2 4 5) (3) (0 1)) ((2 5) (4) (3) (0 1)) ((5) (2 4) (3) (0 1))
((4 5) (2 3) (0 1)) ((5) (4) (2 3) (0 1)) ((3 4 5) (2) (0 1))
((3 5) (4) (2) (0 1)) ((5) (3 4) (2) (0 1)) ((4 5) (3) (2) (0 1))
((5) (4) (3) (2) (0 1)) ((1 2 3 4 5) (0)) ((1 2 3 5) (4) (0))
((1 2 5) (3 4) (0)) ((1 5) (2 3 4) (0)) ((5) (1 2 3 4) (0))
((1 2 4 5) (3) (0)) ((1 2 5) (4) (3) (0)) ((1 5) (2 4) (3) (0))
((5) (1 2 4) (3) (0)) ((1 4 5) (2 3) (0)) ((1 5) (4) (2 3) (0))
((5) (1 4) (2 3) (0)) ((4 5) (1 2 3) (0)) ((5) (4) (1 2 3) (0))
((1 3 4 5) (2) (0)) ((1 3 5) (4) (2) (0)) ((1 5) (3 4) (2) (0))
((5) (1 3 4) (2) (0)) ((1 4 5) (3) (2) (0)) ((1 5) (4) (3) (2) (0))
((5) (1 4) (3) (2) (0)) ((4 5) (1 3) (2) (0)) ((5) (4) (1 3) (2) (0))
((3 4 5) (1 2) (0)) ((3 5) (4) (1 2) (0)) ((5) (3 4) (1 2) (0))
((4 5) (3) (1 2) (0)) ((5) (4) (3) (1 2) (0)) ((2 3 4 5) (1) (0))
((2 3 5) (4) (1) (0)) ((2 5) (3 4) (1) (0)) ((5) (2 3 4) (1) (0))
((2 4 5) (3) (1) (0)) ((2 5) (4) (3) (1) (0)) ((5) (2 4) (3) (1) (0))
((4 5) (2 3) (1) (0)) ((5) (4) (2 3) (1) (0)) ((3 4 5) (2) (1) (0))
((3 5) (4) (2) (1) (0)) ((5) (3 4) (2) (1) (0)) ((4 5) (3) (2) (1) (0))
((5) (4) (3) (2) (1) (0)))