Перестановки двоичного дерева
Вы можете использовать os.path.abspath(f) , чтобы прочитать полный путь к файлу.
Вы можете использовать это, внеся следующие изменения в ваш код.
for root, dirs, files in os.walk(directory):
for f in files:
f_abs = os.path.abspath(f)
if f.startswith('Incidence'):
inc_files2.append(f_abs)
elif f.startswith('Population Count'):
pop_files2.append(f_abs)
6 ответов
Кажется, что самым простым решением был бы обход в глубину Вашего дерева, чтобы собрать все узлы в список, генерировать все перестановки списка, вывести каждую перестановку в двоичное дерево.
Так, учитывая список (+ (+ b c)), у нас есть узлы [a; b; c], которые имеют следующие перестановки:
[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-кортеж является рядом узлов. Для больше, чем нескольких узлов вселенная испытает смерть тепла перед Вашим алгоритмом, когда-либо завершенным.
Эти операции походят на дополнение со следующими свойствами: закрытие, ассоциативность, коммутативность. Для узла соответствия каждый оставляет набор листов тем же и может быть применен рекурсивным способом. Считать перестановки данного узла x (в некотором странном соединении Haskell и F#)
let count x = match x with
| LeafNode -> 1
| TreeNode (a,b) -> 2 * count a * count b
Решение этой проблемы несомнительно собирается включать каталонские числа. Существуют возможные двоичные деревья Cn-1 с листами n, и существуют n! возможные упорядочивания листов, таким образом, существуют n! * Cn-1 возможные деревья. Перечисление их немного более хитро, все же.
Как указано, если у Вас действительно есть коммутативность и аксиомы ассоциативности, Вы лучше всего выключены, просто собрав слагаемых и обработав их как набор или список.
Если это не удовлетворительно, следующая вещь состоит в том, чтобы заметить, что на самом деле Вам, кажется, не нужны все перестановки, но Вы хотите переписать свои выражения для упрощения их. Это может быть сделано намного более эффективным, чем создание всех перестановок!
Однако для повторения :), если у Вас ТОЛЬКО есть коммутативность и ассоциативность, обрабатывают условия в наборе.
У Вас есть ассоциативность и коммутативность, таким образом, можно переместить элементы свободно. Практический подход к этой проблеме - что-то как следующее:
Расчешите дерево одной стороне, Вы получаете список.
Отсортируйте список, так, чтобы элементы, которые должны уравновеситься, были друг рядом с другом.
Переместите элементы в поддерево и отмену.
Для получения желаемого доказательства, необходимо создать маленькие доказательства для них операция, которую Вы затем комбинируете.
Кроме того, Вы могли искать соответствие AC.
Попытка всех перестановок, как Вы предполагаете, просто получит Вас большой combinatorical взрыв.
Я обнаружил решение к базовой проблеме сокращения деревьев:
- Найдите пару листов A и-A от дерева.
- a) Если A и-A находятся в том же ребенке, рекурсивно вызывают.
- b) 'Пузырь' A и-A к вершине их соответствующего childs. Существует восемь возможных получающихся случаев, но они все выглядят примерно так (+ (x A) (-A y)). Движение от этого до (+ (+ x y) (+-A)) легко.
Как предложено, другой способ сделать это состоял бы в том, чтобы сначала преобразовать дерево в список: (+ (+ B (+...)) X), затем найдите пару соответствия A и-A и принесите им к вершине. Я подозреваю, что это может произвести более длинное доказательство (который является нежелательным), чем вышеупомянутый алгоритм, хотя я не попробовал его.
Однако, я нахожу исходный вопрос захватывающим, и я хотел бы попробовать, как алгоритм на основе этого выдержит сравнение с вышеупомянутым.