Это намного проще, чем неограниченный генератор деревьев.
Интересно отметить, что для k элементов существует ровно (k-1)! возможных общих куч. (Если бы мы создавали леса кучи, было бы k! возможных лесов, что эквивалентно генерации одной кучи с новым узлом в качестве root.)
Основная идея заключается в том, что свойство кучи гарантирует, что самый большой элемент любого поддерева является корнем этого поддерева (и, следовательно, самый большой элемент является корнем дерева). Поскольку нам не важен порядок дочерних элементов, мы можем согласиться размещать дочерние элементы в порядке убывания в каждом узле, что гарантирует, что второй по величине элемент в поддереве будет точно самым левым дочерним элементом корня этого поддерева. .
Таким образом, мы можем просто расположить элементы в порядке убывания, повторяя все возможные размещения. После того, как мы сделаем самый большой элемент корнем дерева, каждый последующий элемент, в свою очередь, может стать последним (или единственным) дочерним элементом любого ранее размещенного элемента. (Все ранее размещенные дочерние элементы больше, чем новый элемент, поэтому размещение его на первой позиции поддерживает канонический дочерний порядок. И, конечно, поскольку все ранее размещенные элементы больше, новый элемент может быть дочерним для любого из них.)
С помощью этой процедуры на шаге, где элементы i уже были размещены, можно точно указать i возможных размещений для следующего элемента. Отсюда формула (k-1)!.
Реализация вышесказанного довольно проста, хотя это не что иное, как функциональное решение: дерево кандидатов изменяется на каждом этапе. (Это означает, что вам нужно будет сделать полную копию полученного дерева, если вы намереваетесь изменить его или сохранить его для дальнейшего использования.)
# This differs from the tree object in the other answer because
# in this tree, the kids are modified and must therefore be lists
class tree(object):
def __init__(self, root, kids=()):
self.root = root
self.kids = list(kids)
def __str__(self):
if self.kids:
return "(%s %s)" % (self.root,
' '.join(str(kid) for kid in self.kids))
else:
return self.root
# The main function turns each label into a singleton (leaf) node, and
# then calls the helper function to recursively stitch them together into
# heaps
def allheaps(labels):
if labels:
yield from genheaps(list(map(tree, labels)), 1)
def genheaps(nodes, i):
if i == len(nodes): yield nodes[0]
else:
# For each possible position for node i:
# Place it, recurse the rest of the nodes, restore the parent.
for j in range(i):
nodes[j].kids.append(nodes[i])
yield from genheaps(nodes, i+1)
nodes[j].kids.pop()
Вот шесть куч, построенных из 8, 5, 3, 1:
>>> print('\n'.join(map(str,allheaps("8531"))))
(8 5 3 1)
(8 (5 1) 3)
(8 5 (3 1))
(8 (5 3) 1)
(8 (5 3 1))
(8 (5 (3 1)))
Или, схематично (сделано вручную)
(8 5 3 1) (8 (5 1) 3) (8 5 (3 1)) (8 (5 3) 1) (8 (5 3 1)) (8 (5 (3 1)))
8 8 8 8 8 8
/ | \ / \ / \ / \ | |
5 3 1 5 3 5 3 5 1 5 5
| | | / \ |
1 1 3 3 1 3
|
1
Тот факт, что количество куч является факториалом количества некорневых узлов, говорит о том, что между кучами и перестановками существует изоморфизм. И действительно, как видно из приведенных выше диаграмм, это действительно так.
Мы можем превратить кучу в перестановку, выполнив обход дерева в порядке глубины после заказа. Обход после заказа гарантирует, что последний узел в обходе будет корнем.
Чтобы пойти другим путем, от перестановки, заканчивающейся корневой меткой, до кучи, мы инициализируем пустой стек и сканируем перестановку слева направо. Мы помещаем каждую метку в стек после того, как сначала заполним его дочерний список, выталкивая любые меньшие элементы из верхней части стека. Если перестановка заканчивается самым большим элементом, он будет единственным элементом в стеке в конце сканирования. (Если бы мы допустили произвольные перестановки, мы бы получили n! леса кучи вместо (n-1)! укорененных кучи.)
Это говорит о том, что мы могли бы перечислять кучи, используя любой удобный метод перечисления перестановок и построения кучи из перестановки:
from itertools import permutations
from functools import reduce
def putlabel(stk, label):
kids=[]
while stk and stk[-1].root < label: kids.append(stk.pop())
stk.append(tree(label, kids))
return stk
def permtoheap(root, perm):
'''Construct a heap with root 'root' using the non-root nodes from
a postorder walk. 'root' should be larger than max(perm); otherwise,
the result will not satisfy the heap property.
'''
return tree(root, reduce(putlabel, perm, []))
def allheaps2(labels):
if labels:
yield from (permtoheap(labels[0], p) for p in permutations(labels[1:]))