Пролог, реконструировать деревья BST из списка по порядку

Question

Мы хорошо знаем inorder реализация для дерева BST.

inorder(nil, []).
inorder(t(Root, L, R), List) :-
    inorder(L, ListLeft),
    inorder(R, ListRight),
    append(ListLeft, [Root|ListRight], List).

Однако возможно ли это сделать для списка? Я имею в виду реконструировать все возможные деревья BST, например:

inorder(X, [1,2,3]).
X = t(1, nil, t(2, nil, t(3, nil, nil))));
X = t(3, t(2, t(1, nil, nil), nil), nil), nil);
X = t(2, t(1, nil, nil), t(3, nil, nil));
false.

Это кажется невозможным для меня.

Answer 1

Во-первых, давайте используем грамматику "Определенное предложение" ( dcg) для привязки деревьев к спискам:

Inorder (ноль) -> [].
inorder(t(Root, L, R)) ->
    Симметричный (L)
    [Root],
    Симметричный (R).

Уловка, которую я теперь буду применять, описана в диссертации Ульриха Ноймеркеля в " Укрощении левой рекурсии".

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

В нашем случае:

inorder (ноль, Es, Es) -> [].
inorder (t (Root, L, R), [_ | Es0], Es) ->
    порядок (L, Es0, Es1),
    [Root],
    Inorder (R, Es1, Es).

Пример запроса (Ls опущены):

? - Ls = [1,2,3], фраза (inorder(Tree, Ls, _), Ls).
Tree = t(1, ноль, t(2, ноль, t(3, ноль, ноль)));
Tree = t(1, ноль, t(3, t(2, ноль, ноль), ноль));
Tree = t(2, t(1, ноль, ноль), t(3, ноль, ноль));
Tree = t(3, t(1, ноль, t(2, ноль, ноль)), ноль);
Tree = t(3, t(2, t(1, ноль, ноль), ноль), ноль);
ложный.

Другим способом решения таких проблем является использование механизма табулирования вашей системы Prolog.

Answer 2

Если вам нравится трюк, который я предложил здесь, единственное необходимое изменение может быть

: - use_module (carlo ( snippets / when_)).

inorder(t(Root, L, R), List) -:- ...

и сейчас

?- inorder(T,[1,2,3]).
T = t(1, nil, t(2, nil, t(3, nil, nil))) ;
T = t(1, nil, t(3, t(2, nil, nil), nil)) ;
T = t(2, t(1, nil, nil), t(3, nil, nil)) ;
T = t(3, t(1, nil, t(2, nil, nil)), nil) ;
T = t(3, t(2, t(1, nil, nil), nil), nil) ;
false.