python - 完全な (ラベル付きの) 二分木をすべて列挙する

Question

完全にラベル付けされた二分木をすべて列挙するための実用的なアルゴリズムを探しています。

完全な二分木は、すべての内部ノードの次数が 3、リーフの次数が 1、ルートの次数が 2 のツリーです。

ラベル付きツリーは、すべての葉が一意のラベルを持つツリーです。

例：

    *
    |\
    | \
    *  *
   /|  |\
  / |  | \
 T  C  D  F

Answer 1

コメントから、問題は、ルート化された順序付けられていないラベル付きの完全な二分木を列挙することであることは明らかです。この論文で説明されているように、nラベルが付いたそのような木の数は次のとおりです。(2n-3)!!ここ!!で、は超階乗関数です。

次のPythonプログラムは、参照されている論文の再帰的証明に基づいています。コードは、アルゴリズムの説明として渡されるほど単純明快だと思います。

# A very simple representation for Nodes. Leaves are anything which is not a Node.
class Node(object):
  def __init__(self, left, right):
    self.left = left
    self.right = right

  def __repr__(self):
    return '(%s %s)' % (self.left, self.right)

# Given a tree and a label, yields every possible augmentation of the tree by
# adding a new node with the label as a child "above" some existing Node or Leaf.
def add_leaf(tree, label):
  yield Node(label, tree)
  if isinstance(tree, Node):
    for left in add_leaf(tree.left, label):
      yield Node(left, tree.right)
    for right in add_leaf(tree.right, label):
      yield Node(tree.left, right)

# Given a list of labels, yield each rooted, unordered full binary tree with
# the specified labels.
def enum_unordered(labels):
  if len(labels) == 1:
    yield labels[0]
  else:
    for tree in enum_unordered(labels[1:]):
      for new_tree in add_leaf(tree, labels[0]):
        yield new_tree

のためn == 4に、(2*4 - 3)!! == 5!! == 1 * 3 * 5 == 15木があります：

>>> for tree in enum_unordered(("a","b","c","d")): print tree
... 
(a (b (c d)))
((a b) (c d))
(b (a (c d)))
(b ((a c) d))
(b (c (a d)))
(a ((b c) d))
((a (b c)) d)
(((a b) c) d)
((b (a c)) d)
((b c) (a d))
(a (c (b d)))
((a c) (b d))
(c (a (b d)))
(c ((a b) d))
(c (b (a d)))

質問の別の考えられる解釈は、ラベルの指定されたリストを持つルート化された順序付けられた完全な二分木の列挙を求めたというものでした。n枚の葉を持つそのような木の数は、カタラン数列から、によって与えられます。Cn-1

def enum_ordered(labels):
  if len(labels) == 1:
    yield labels[0]
  else:
    for i in range(1, len(labels)):
      for left in enum_ordered(labels[:i]):
        for right in enum_ordered(labels[i:]):
          yield Node(left, right)

5つのラベルの場合、次のようになります。C5-1 == 14

>>> for tree in enum_ordered(("a","b","c","d", "e")): print tree
... 
(a (b (c (d e))))
(a (b ((c d) e)))
(a ((b c) (d e)))
(a ((b (c d)) e))
(a (((b c) d) e))
((a b) (c (d e)))
((a b) ((c d) e))
((a (b c)) (d e))
(((a b) c) (d e))
((a (b (c d))) e)
((a ((b c) d)) e)
(((a b) (c d)) e)
(((a (b c)) d) e)
((((a b) c) d) e)