Изоморфизм бинарных деревьев

Question

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

Вот то, что я имею до сих пор, это работает за исключением возврата дубликатов.

% Clause: btree_iso
%
% Specification:
% --------------
% Satisfied when the two binary-tree parameters are isomorphic. Two binary
% trees are isomorphic if one can be derived from the other by changing the
% order of the branches. Either of the parameters may be instantiated with a
% variable when btree_iso is used in a top-level goal.
%
% Description:
% ------------
% Base case for the binary tree iso morphism predicate.
% Both sides are leaves.
btree_iso( leaf, leaf ).

% Description:
% ------------
% TODO
btree_iso( node( BTL1, X, BTR1 ), node( BTL2, X, BTR2 ) ) :- btree_iso( BTL1, BTL2 ),
                                                             btree_iso( BTR1, BTR2 ).
% Description:
% ------------
% TODO
btree_iso( node( BTL1, X, BTR1 ), node( BTL2, X, BTR2 ) ) :- btree_iso( BTL1, BTR2 ),
                                                             btree_iso( BTR1, BTL2 ).

Ожидаемый результат:

? - btree_iso(node(node(leaf,3,leaf),3,node(leaf,5,leaf)),BT).
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)).

Мой вывод

?- btree_iso(node(node(leaf,3,leaf),3,node(leaf,5,leaf)),BT).
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)).

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

Любой совет, как я могу остановить дубликаты?

Answer 1

Подумайте о том, что происходит, когда BT = узел (лист, X, лист). Ваше решение дает два идентичных решения для этого случая. Один, где листья поменялись местами, а другой - нет.

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