Как сгенерировать все деревья, имеющие n-узлы и глубину m-уровня? Коэффициент ветвления является переменным и не должен быть постоянным внутри самого дерева

Question

Я полагаю, довольно простой вопрос.

Например, алгоритм уровня 5 с 5 узлами исключит

 A
 |
 B
 |
 C
 |
 D
 |
 E 

но нет

    A
   /|\
  B C D
       \
        E

что так же, как (по крайней мере для меня)

    A
   /|\
  D C B
 /
E

Например, алгоритм 3-Node 2-Level генерирует только следующее:

   (1)               (2)             (3)

    A                 B               C
   / \        or     / \       or    / \ 
  B   C             A   C           A   B

Обратите внимание, что я считаю дерево ниже таким же, как (2) выше:

       B
      / \
     C   A

Answer 1

Базовая структура решения будет рекурсивной, хотя точные детали меняются в зависимости от классов точной эквивалентности, которые вы принимаете для генерации. Здесь вам нужно будет рассмотреть такие вопросы, как, помечены ли узлы или нет, и упорядочены ли дочерние узлы или нет. Каждый из этих вариантов определяет очень разные, но одинаково интересные проблемы поколения.

Основной алгоритм состоит в том, чтобы выяснить перечисление возможных наборов дочерних элементов, подчиняющихся классам эквивалентности, определенным для конкретной задачи, путем создания только канонической записи для каждого класса эквивалентности. Например, для немаркированных деревьев с упорядоченными дочерними элементами мы могли бы начать с перечисления всех упорядоченных разделов числа узлов; для данного раздела мы сформируем декартово произведение всех возможных возможных поддеревьев указанных размеров. Если бы мы не заботились о порядке детей, нам нужно было бы найти какой-нибудь способ составления канонических списков детей: мы могли бы сначала отсортировать поддеревья по общему размеру, но затем нам нужен канонический порядок для двух поддеревьев. того же размера. Это сложно, но есть решения.

Я понимаю, что ваша проблема состоит не только в количестве узлов, но и в специфических метках узлов, и поэтому два дерева одинаковой формы, но с разными метками должны рассматриваться как разные. Однако вы хотите, чтобы порядок детей не имел отношения к сравнению. Тот факт, что все узлы имеют уникальные метки, делает проблему вполне решаемой: мы можем перечислять непустые подмножества доступных меток, потому что мы знаем, что деревья, сгенерированные с одним подмножеством меток, должны отличаться от деревьев, сгенерированных с другим подмножеством., Поскольку сами поддеревья неупорядочены, мы можем канонизировать, сохранив отсортированные корни поддеревьев (любое упорядочение так же хорошо, как и любое другое).

Таким образом, мы в конечном итоге с процедурой GenTrees(R, D, N), где R это корневая метка, D набор меток-потомков, и N максимальная глубина дерева, которая может быть определена следующим образом:

• Если D пусто, возвращает одноэлементное множество с деревом, состоящим только из указанного корневого узла.

• (Для эффективности) Если N равен 1, возвращает одноэлементное множество с деревом, состоящим из указанного корневого узла с оставшимися узлами в виде листьев. (Менее эффективным шагом является "Если N 0, вернуть пустой набор."Но лучше ярлык, проверив N == 1.)

• В противном случае начните с пустого набора возможных деревьев и

• Для каждого непустого подмножества S из D (это дочерние элементы корневого узла):

  • За каждый заказанный раздел P из D - S в |S| подмножества (это оставшиеся потомки каждого поддерева):

    • Добавить к возвращаемому множеству все деревья с корнем R чьи дети в GenTrees(Si, Pi, N-1), (Это декартово произведение. Здесь порядок S произвольно, но должно быть согласованным; сортировка меток в порядке возрастания была бы очевидным решением.)

Чтобы немного протестировать вышесказанное, я написал пример реализации на Python. Он не пытается быть эффективным, и в основном это транскрипция вышеупомянутого с использованием генераторов Python. (Преимущество генераторов в том, что нам не нужно заполнять память миллионами возможных деревьев; мы просто генерируем по одному за раз.)

В случае, если это яснее, чем словоблудие, вот оно:

from functools import reduce
from itertools import product

class tree(object):
  def __init__(self, root, kids=()):
    self.root = root
    self.kids = tuple(kids)

  def __str__(self):
    '''Produce an S-expr for the tree.'''
    if self.kids:
      return "(%s %s)" % (self.root,
                          ' '.join(str(kid) for kid in self.kids))
    else:
      return self.root

def append(part, wherewhat):
  part[wherewhat[0]].append(wherewhat[1])
  return part

def gentrees(root, labels, N):
  if not labels or N <= 1:
    yield tree(root, labels if N else ())
  else:
    for p in product((0,1), repeat = len(labels)):
      if any(p):
        nexts, roots = reduce(append, zip(p, labels), ([], []))
        for q in product(range(len(roots)), repeat = len(nexts)):
          kidsets = reduce(append, zip(q, nexts), tuple([] for i in roots))
          yield from (tree(root, kids)
                      for kids in product(*(gentrees(root, rest, N-1)
                                            for root, rest in zip(roots, kidsets))))    

def alltrees(labels, N):
  for i, root in enumerate(labels):
    yield from gentrees(root, labels[:i] + labels[i+1:], N)

Последняя функция перебирает все возможные корни и вызывает гентри с каждым из них. Вот пример выходных данных для трех узлов и максимальной глубины 2 (эта функция считает глубину в ссылках, а не в узлах):

>>> print('\n'.join(map(str,alltrees("ABC",2))))
(A (C B))
(A (B C))
(A B C)
(B (C A))
(B (A C))
(B A C)
(C (B A))
(C (A B))
(C A B)

Стоит отметить, что количество сгенерированных деревьев увеличивается экспоненциально с количеством меток узлов. Если вы не ограничиваете себя очень маленькими деревьями, вам, вероятно, следует попытаться по возможности сократить рекурсию поколения (сверху вниз или снизу вверх или и то, и другое).