在Prolog中列举顺序

Question

我试图通过将inorder列表转回BST来"反转"inorder遍历.

BST具有谓词形式node(Value,Left,Right)或者leaf,因此空树只是leaf一棵树,一个节点就是node(_,leaf,leaf).

给定谓词enumerate_bst(Elems,Bst),目标是匹配Bstinorder列表的所有可能性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列表:

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**

我们希望它只是显示这个唯一的解决方案,然后停止.实际原因是程序的以下片段 - 故障片.无需进一步了解.换句话说,根本不需要理解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目标放在第一位.这一工程(即,它终止了地面第二个参数),但它是相当不满意的,因为程序是现在投入到分发列表的元素融入树木只.

这是一个双向工作的版本,如终止条件所示:

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