Перестановки двоичного дерева

Question

Рассмотрим двоичное дерево:

1. n - это узел, если n - это целое число
2. (+ a b ) является узлом, если a и b являются узлами.

У нас есть следующие три операции:

1. (+ a b ) -> (+ b a )
2. (+ (+ a b ) c ) -> (+ a (+ b с ))
3. (+ a (+ b c )) -> (+ (+ a b ) c ) - (2. в обратном порядке)

Мне нужен алгоритм для предоставления всех возможных перестановок данного дерева с помощью этих операций. Любая операция может быть применена к любому поддереву. Под перестановкой я подразумеваю любое дерево, которое имеет точно такой же набор листьев. Это, вероятно, не очень сложно, но я просто не могу понять это.

[Edit] Листья также могут быть именами (то есть переменными), поэтому полагаться на их свойства в виде целых чисел нельзя. Деревья представляют суммы.

[Edit2] Смысл этого упражнения в том, чтобы уменьшить сумму, найдя члены в форме A и -A , свернув дерево, чтобы превратить их в поддерево (+ A -A ), чтобы устранить их. Три операции, приведенные выше, являются аксиомами в моей системе, и их необходимо использовать полностью, иначе невозможно доказать, что уменьшенное дерево равно оригиналу. Поскольку я использую Twelf язык логического программирования, если мне удастся найти алгоритм для выполнения того, что я первоначально просил, остальное следует легко, но альтернативные решения, конечно, приветствуются.

Answer 1

Похоже, что самым простым решением было бы обход вашего дерева в глубину, чтобы собрать все узлы в список, сгенерировать все перестановки списка, сбросить каждую перестановку в двоичное дерево.

Итак, учитывая список (+ a (+ b c)), у нас есть узлы [a; б; с], которые имеют следующие перестановки:

[a; b; c]
[a; c; b]
[b; a; c]
[b; c; a]
[c; a; b]
[c; b; a]

Первый элемент в списке - это ваша голова, следующие два элемента - это дочерние узлы, следующие четыре элемента - это дочерние узлы и т. Д.

Сложность этого резко возрастает , если вам нужно составить список всех возможных деревьев, а не только сбалансированных. В этом случае вам нужно сгруппировать их следующим образом:

[a; b; c; d]
[(a; b); c; d]
[(a; b; c); d]
[a; (b; c); d]
[a; (b; c; d)]
[a; b; (c; d)]
[a; b; d; c]
// first permutation
[(a; b); d; c]
[(a; b; d); c]
...

Где каждый n-кортеж - это набор узлов. Для более чем нескольких узлов вселенная испытает тепловую смерть, прежде чем ваш алгоритм когда-либо завершится.

Answer 2

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

Если это неудовлетворительно, то следует заметить, что на самом деле вам не нужны все перестановки, но вы хотите переписать свои выражения, чтобы упростить их. Это можно сделать намного эффективнее, чем производить все перестановки!

Однако, чтобы повторить :), если у вас ТОЛЬКО коммутативность и ассоциативность, обрабатывайте термины в наборе.

Answer 3

У вас есть ассоциативность и коммутативность, поэтому вы можете свободно перемещать элементы. Практический подход к этой проблеме выглядит примерно так:

• Расчесав дерево в одну сторону, вы получите список.

• Сортировка списка так, чтобы элементы, которые должны быть отменены, были рядом друг с другом.

• Переместите элементы в поддерево и отмените.

Чтобы получить желаемое доказательство, вы должны создать небольшие доказательства для этой операции, которые затем объедините.

В качестве альтернативы вы можете посмотреть соответствие AC.

Попытка всех перестановок, как вы предлагаете, просто вызовет большой комбинаторный взрыв.

Answer 4

Эти операции аналогичны сложению со следующими свойствами: замыкание, ассоциативность, коммутативность. Для совпадающего узла каждый оставляет набор листьев одинаковым и может быть применен рекурсивным способом. Подсчитать перестановки заданного узла x (в какой-то странной смеси Haskell и F #)

let count x = match x with
  | LeafNode -> 1
  | TreeNode (a,b) -> 2 * count a * count b

Answer 5

Решение этой проблемы, несомненно, будет включать каталонские числа . Есть C _{n -1} возможных бинарных деревьев с n листьями, и есть n ! Возможны упорядочения листьев, поэтому есть n ! * C _{n -1} возможных деревьев. Перечислять их немного сложнее.

Answer 6

Я нашел решение основной проблемы сокращения деревьев:

1. Найдите пару листьев A и -A на дереве.
2. a) Если A и -A принадлежат одному и тому же ребенку, выполните рекурсию.
3. b) «Пузырь» А и -А на вершину их соответствующих детей. Есть восемь возможных результирующих случаев, но все они выглядят примерно так (+ (x A) (-A y)). Переход от этого к (+ (+ x y) (+ A -A)) очень прост.

Как и предполагалось, другой способ сделать это - сначала преобразовать дерево в список: (+ A (+ B (+ ...)) X), затем найти подходящую пару A и -A и привести их к началу. Я подозреваю, что это может привести к более длинному доказательству (что нежелательно), чем приведенный выше алгоритм, хотя я не пробовал его.

Тем не менее, я нахожу оригинальный вопрос увлекательным, и я хотел бы попробовать, как алгоритм, основанный на этом, будет сравниваться с вышеупомянутым.