prolog - 在 Prolog 中枚举顺序

Question

我试图通过将中序列表转回 BST 来“反转”中序遍历。

BSTs 有谓词形式 node(Value,Left,Right) 或 leaf，所以空树就是 leaf，一棵树一个节点是 node(_,leaf,leaf)。

给定谓词 enumerate_bst(Elems,Bst)，目标是将 Bst 与中序列表 Elems 的所有可能性相匹配。例如(注意 setof/3 ):

?- setof(Bst,enumerate_bst([],Bst),Enum).
Enum = [leaf].

?- setof(Bst,enumerate_bst([1,2],Bst),Enum).
Enum = [
    node(1, leaf, node(2, leaf, leaf)),
    node(2, node(1, leaf, leaf), leaf)
].

?- setof(Bst,enumerate_bst([1,2,3],Bst),Enum).
Enum = [
    node(1, leaf, node(2, leaf, node(3, leaf, leaf))),
    node(1, leaf, node(3, node(2, leaf, leaf), leaf)),
    node(2, node(1, leaf, leaf), node(3, leaf, leaf)),
    node(3, node(1, leaf, node(2, leaf, leaf)), leaf),
    node(3, node(2, node(1, leaf, leaf), leaf), leaf)
].

我尝试做的事情:

我已经有一个谓词将给定的 BST 与其中序列表相匹配:

inorder(leaf,[]).
inorder(node(X,L,R),Elems) :-
  inorder(L,Elems_L),
  inorder(R,Elems_R),
  append(Elems_L,[X],Tmp),
  append(Tmp,Elems_R,Elems).

我试图通过放入一个列表来反向使用它，但这只返回了一个结果，我不确定为什么。

我目前正在尝试做什么

我正在尝试使用 native 谓词 append/3相反，但不能完全决定如何完成。

关于执行此操作的最佳方法有什么想法吗？谢谢!

Answer 1

相反，您的程序不会终止。考虑:

?- inorder(Tree, []).
   Tree = leaf
;  loops.

我们希望它只显示这个唯一的解决方案然后停止。实际原因是您程序的以下片段 - failure-slice .无需再看下去了。换句话说，根本不需要理解 append/3。

?- inorder(Tree, []), false.inorder(leaf,[]) :- false.inorder(node(X,L,R),Elems) :-   inorder(L,Elems_L), false.   inorder(R,Elems_R),   append(Elems_L,[X],Tmp),   append(Tmp,Elems_R,Elems).

First, this fragment needs to terminate (and fail). Only then you may consider termination of the entire program. Within this fragment, the second argument (Elems) is completely ignored! The first goal that would be interested in it is the very last one (append(Tmp,Elems_R,Elems)).

A naive way out would be to reorder the goals, putting the two append/3 goals first. That works (that is, it terminates for a ground second argument), but it is quite unsatisfying, as the program is now devoted to distributing elements of a list into trees only.

Here is a version that works both ways as indicated by the termination condition:

inorder(A,B)terminates_if b(A);b(B).

which states that inorder/2 terminates if the first or the second argument is ground.

inorder(Tree, Xs) :-
   phrase(inorder(Tree, Xs,[]), Xs).

inorder(leaf, Vs,Vs) -->
   [].
inorder(node(X,L,R), [_|Vs0],Vs) -->
   inorder(L, Vs0,Vs1),
   [X],
   inorder(R, Vs1,Vs).