Prolog、インオーダーリストからBSTツリーを再構築

Question

BSTツリーの実装にはinorderがよく知られています。

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(nil) --> []. 
inorder(t(Root, L, R)) --> 
    inorder(L), 
    [Root], 
    inorder(R). 

私は今使いこなす左再帰でウルリッヒNeumerkelのdissertationに記述されて適用されますトリックを。

「...私たちは、新たに発生した非終端で使用できるトークンの数のための別の状態を追加します。単一のルール内の端末によって読み取られるトークンの数は、従って、事前に予約されています。」我々の場合には

：

 
inorder(nil, Es, Es) --> []. 
inorder(t(Root, L, R), [_|Es0], Es) --> 
    inorder(L, Es0, Es1), 
    [Root], 
    inorder(R, Es1, Es). 

サンプル・クエリ（Lsは省略）：

 
?- Ls = [1,2,3], phrase(inorder(Tree, Ls, _), Ls). 
Tree = t(1, nil, t(2, nil, t(3, nil, nil))) ; 
Tree = t(1, nil, t(3, t(2, nil, nil), nil)) ; 
Tree = t(2, t(1, nil, nil), t(3, nil, nil)) ; 
Tree = t(3, t(1, nil, t(2, nil, nil)), nil) ; 
Tree = t(3, t(2, t(1, nil, nil), nil), nil) ; 
false. 

、このような問題を解決するもう一つの方法は、あなたのPrologシステムのテーブル化メカニズムを使用することです。

Answer 2

あなたがプロローグを学ぶことを真剣に考えている場合、私はhereを提案してきたトリックのような場合は、必要な唯一の変更は

 
:- 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.