algorithm - カタロニア語の関係で並べ替えられたすべてのバイナリ ツリーを一覧表示する方法

Question

Lisp または疑似コードで、カタロニア語の関係で並べ替えられたすべてのバイナリ ツリーを一覧表示するアルゴリズムを探しています。

たとえば、入力で次の'(a b c d)結果が得られます。(a (b (c d))) (a ((b c) d)) ((a b) (c d)) ((a (b c)) d) (((a b) c) d)

助けてくれてありがとう。

Answer 1

カタロニア語の数は、バイナリ ツリーの特定の順序を定義しません。最も一般的な順序付けは、葉の深さの辞書式順序の降順です (したがって、左に重いツリーがバランスのとれたツリーの前に並べられ、バランスのとれたツリーが右に重いツリーの前に並べられます)。

この順序付けを取得するには、n葉のあるツリーに再帰アルゴリズムを使用できます。このアルゴリズムはa+b=n, a>=1, b>=1、 の降順で、葉のある左側の子と葉のある右側の子aから構成されるすべてのツリーを返します。つまり、両側で再帰し、デカルト積を出力します。ab

擬似コード:

def gen_trees(a,b):
    left_trees = gen_all_trees(a)
    right_trees = gen_all_trees(b)

    trees = []
    for l in left_trees:
        for r in right_trees:
            trees.append([l,r])
    return trees

def gen_all_trees(items):
    trees = []
    if len(items) == 1:
        trees += [items[0]]
    else:
        for i in range(len(items)-1, 0,-1):
            a = items[:i]
            b = items[i:]
            trees += gen_trees(a,b)
    return trees