# 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)))
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)
从评论中可以清楚地看出,问题是枚举有根的无序标记的全二叉树。如this paper中所述,具有
n
标签的此类树的数量为(2n-3)!!
,其中!!
为double factorial function下面的python程序基于参考文献中的递归证明;我认为代码足够直截了当,可以作为算法的解释:
对于
n == 4
,有(2*4 - 3)!! == 5!! == 1 * 3 * 5 == 15
树:对这个问题的另一种可能的解释是,它试图枚举具有指定标签列表的根有序完整二叉树。这种有n片叶子的树的数量由
Cn-1
给出,从Catalan number sequence开始对于5个标签,我们有
C5-1 == 14
:相关问题 更多 >
编程相关推荐