2

在上一篇文章中，我最终想出了如何编写 gprolog 程序来检查一个列表是否是另一个列表的排列。据我所知，它有效。

现在，我正在创建一个mysort谓词，它将排列谓词与这个组合谓词（据我所知，也可以工作）：

sorted([]).   
sorted([L]) :- !.  
sorted([L|[T|TT]]) :- L @=< T, sorted([T|TT]).

由于我的原始perm谓词设计为!在得到答案后立即终止，因此我进行了一些修改以允许mysort检查可能性。这是mysort，它的特殊backtrack_perm，以及与旧的重叠perm（我只是将其修改为对 的轻微更改backtrack_perm）：

perm([],[]).
perm([LH|LT],R) :-
   backtrack_perm([LH|LT],R),
   !.

perm_recurse([],X). 
perm_recurse([LH|LT],R) :-
   member(LH,R),
   select(LH,[LH|LT],X),
   select(LH,R,Y),
   perm_recurse(X,Y),
   !. 

mysort(L,M) :-
   backtrack_perm(L,M),
   sorted(M),
   !.  

backtrack_perm([],[]).
backtrack_perm([LH|LT],R) :-
   length([LH|LT],A),
   length(R,B),
   A == B,
   member(LH,R),
   select(LH,[LH|LT],X),
   select(LH,R,Y),
   perm_recurse(X, Y).

尽管它的组件看起来可以正常工作，但mysort在某些输入上会导致堆栈溢出，例如mysort([5,3,2],X). 在已经排序的列表中，例如mysort([2,3,5],X)，甚至是部分列表中，mysort([3,2,5],X)跟踪可能很长，但它确实得到了答案。正因为如此——而且由于一个较小的完全向后的列表[2,1]可以正常工作——我认为问题在于该过程本身对于所有这些排列来说太耗费空间/时间。

如果不深入研究更长的痕迹，是否可以安全地假设是这种情况？或者 Prolog/计算机应该能够毫无困难地处理这个问题，这意味着我需要重新考虑算法？

4

1 回答 1

5

@Will Ness 已经为您提供了perm/2. 但是让我们看看你的程序。实际上，您的行为非常奇怪：有时它似乎有效，有时则无效。我们如何缩小范围？正如您亲身经历的那样，追踪似乎不是一种选择。

这是一种特殊的调试技术，称为切片。我将通过插入目标来稍微修改您的程序以查看发生了什么false。生成的程序称为故障片。我将使用查询：

?- mysort([1],[2|_]).
Fatal Error: global stack overflow

显然，具有单个1as 元素的列表不能对应于以 开头的列表2。所以理想情况下，这应该失败。它不可能那么复杂。它可以？

@larsmans 已经给了你一个提示，但我会自己尝试一下。我会将以下目标添加false到您的计划中。以这种方式，某些部分将永远不会被调用，它们会被删除。并且某些谓词根本不会被调用，所以我不再展示它们：

?- mysort([1],[2|_])。

我的排序（L，M）：-
   backtrack_perm(L,M), false ,
    sorted(M) ,
    ! .  

backtrack_perm([],[]) :- false。
backtrack_perm([LH|LT],R) :-
   长度（[LH|LT]，A），
   长度（R，B），假，
    A == B，
   成员（LH，R），
   选择（LH，[LH|LT]，X），
   选择（LH，R，Y），
    perm_recurse（X，Y）。

这个故障片在某种意义上和你的程序一样糟糕：同样，它不会终止。但它更小。要解决这个问题，你必须在那个片段中做一些事情。因为，只要那部分保持原样，问题就会持续存在。

在这种情况下，length(R,B)罪魁祸首是目标：变量B第一次出现在此处，因此未实例化。而且也是R未实例化的。目标的答案是什么length(R, B)。试试看！

| ?- 长度（R，B）。

B = 0
R = [] ? ;

B = 1
R = [_]？;

B = 2
R = [_,_] ? ;

B = 3
R = [_,_,_] ? ;

B = 4
R = [_,_,_,_] ? ;

B = 5
R = [_,_,_,_,_] ? ...

所以有无数个答案。因此，您的程序不会终止。

length(R, B), A == B通过替换 可以轻松解决此问题length(R, A)。

| ?- mysort([9,1,2,3,4,5,6,7,8],L)。

L = [1,2,3,4,5,6,7,8,9]

(21841 毫秒) 是

多说几句：!你的程序里有红切，它们可能会给你带来很多麻烦。然后，执行时间并没有那么长：对 9 个元素进行排序需要 21 秒，这听起来并不酷。但请记住，您的描述本质上是说：我想要一个排列，即升序。你不要说更多。鉴于信息非常稀缺，Prolog 至少能够找到正确的答案。它甚至非常节省空间。

如何将此程序变成更高效的程序，请参阅此答案。

于 2013-07-06T22:13:07.983 回答