在 Prolog 中枚举顺序

Question

我正在尝试 "reverse" 通过将中序列表转回 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).

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

我目前正在尝试做什么

我正在尝试反向使用本机谓词 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).

首先，这个片段需要终止（并失败）。只有这样你才可以考虑终止整个程序。在这个片段中，第二个参数 (Elems) 被完全忽略了！第一个感兴趣的目标是最后一个 (append(Tmp,Elems_R,Elems))。

一个天真的出路是重新排列目标，将两个 append/3 目标放在首位。 That works（也就是说，它终止于第二个参数），但它并不令人满意，因为该程序现在致力于将列表的元素分布到树中 only。

这里是一个可以工作的版本 both ways 如终止条件所示：

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

其中指出，如果第一个或第二个参数为基础，inorder/2 将终止。

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

Answer 2

前段时间我为这个任务写了一个'library'。使用那个：

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

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

然后

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

您的代码的唯一更改（除了包含 'library'）是将 :- 替换为 -:-。我选择了暗示双向性的符号...

在 Prolog 中枚举顺序

Enumerate inorder in Prolog

prolog

binary-search-tree

dcg

failure-slice