Я пытаюсь создать структуру данных, которая будет описывать определенный тип рекомбинирующего дерева «комбинаций» (аналогично здесь ).
Сначала рассмотрим дерево, в котором каждый узел имеет определенный идентификатор, который описывается последовательностью, необходимой для достижения узла.В качестве примера возьмем фиксированный список Q = [1,2,3] и скомпоноваем возможные перестановки Q в дерево T на основе диаграммы последовательности S:
S =
_0_
/ | \
1 2 3
/| / \ |\
2 3 1 3 1 2
| | | | | |
3 2 3 1 2 1
Затем даем каждому узлу букву, A, B, C,... дерево T может быть представлено как:
T =
_0_
/ | \
A B C
/| / \ |\
D E F G H I
| | | | | |
J K L M N O
где
A = {1}
B = {2}
C = {3}
D = {1,2}
E = {1,3}
F = {2,1}
G = {2,3}
H = {3,1}
I = {3,2}
J = {1,2,3}
K = {1,3,2}
L = {2,1,3}
M = {2,3,1}
N = {3,1,2}
O = {3,2,1}
Теперь моя цель состоит в том, чтобы создать такую структуру данных, чтобы дерево, котороерекомбинирует таким образом, что узлы J и L являются одним и тем же объектом (т.е. рекомбинируют), и аналогично K и N рекомбинируют, и, наконец, M и O рекомбинируют.Правило рекомбинации состоит в том, что их родители D и F, E и H, а также G и I содержат одинаковые элементы, а следующий элемент в последовательности идентичен.Более подробно, правило, приводящее к эквивалентности между J и L, состоит в том, что их "родители" D и F устанавливаются эквивалентными (= {1,2}).Я не уверен, как это выглядело бы для больших списков Q ...
У деревьев, подобных этому, есть определенное имя?Существуют ли какие-либо ресурсы, на которые я должен обратить внимание, или какие-либо места, с которых я должен начать?Спасибо!