4

这是我的第一个想法： 

perm([X|Y],Z) :- takeout(X,Z,W), perm(Y, W).   
perm([],[]).

当我尝试运行-? perm([1, 2, 3], P).时，它显示了堆栈溢出问题。

但是如果我们改变这两个语句的顺序，它就会起作用。 

perm([X|Y],Z) :- perm(Y, W), takeout(X,Z,W).  
perm([],[]).

为什么？我是Prolog初学者，请帮忙。

4

4 回答 4

2

你所指的takeout/3就是俗称的select(X, Xs0, Xs)

这是另一个定义 - 说明 DCG 的不常见用法。

perm(Xs,Ys) :-
   phrase(perm(Xs),[],Ys).

perm([]) --> [].
perm([X|Xs]) --> perm(Xs), ins(X).

ins(X),[X] --> [].
ins(X),[Y] --> [Y], ins(X).
于 2011-11-11T14:22:10.870 回答
0

好吧，您的takeout谓词可能如下所示：

takeout( X, [X|R], R ).
takeout( X, [F|R], [F|S] ) :-
    takeout( X, R, S ).

SWI-Prolog 有一个有用的谓词，名为trace.

在第一种情况下：

X = [1, 2, 3] ;
   Redo: (10) takeout(3, _G477, _G485) ? creep
   Call: (11) takeout(3, _G480, _G483) ? creep
   Exit: (11) takeout(3, [3|_G483], _G483) ? creep
   Exit: (10) takeout(3, [_G479, 3|_G483], [_G479|_G483]) ? creep
   Call: (10) perm([], [_G479|_G483]) ? creep
   Fail: (10) perm([], [_G479|_G483]) ? creep
   Redo: (11) takeout(3, _G480, _G483) ? creep
   Call: (12) takeout(3, _G486, _G489) ? creep
   Exit: (12) takeout(3, [3|_G489], _G489) ? creep
   Exit: (11) takeout(3, [_G485, 3|_G489], [_G485|_G489]) ? creep
   Exit: (10) takeout(3, [_G479, _G485, 3|_G489], [_G479, _G485|_G489]) ? creep
   Call: (10) perm([], [_G479, _G485|_G489]) ? creep
   Fail: (10) perm([], [_G479, _G485|_G489]) ? creep
   Redo: (12) takeout(3, _G486, _G489) ? creep
   Call: (13) takeout(3, _G492, _G495) ? creep
   Exit: (13) takeout(3, [3|_G495], _G495) ? creep
   Exit: (12) takeout(3, [_G491, 3|_G495], [_G491|_G495]) ? creep
   Exit: (11) takeout(3, [_G485, _G491, 3|_G495], [_G485, _G491|_G495]) ? creep
   Exit: (10) takeout(3, [_G479, _G485, _G491, 3|_G495], [_G479, _G485, _G491|_G495]) ? creep
   Call: (10) perm([], [_G479, _G485, _G491|_G495]) ? creep
   Fail: (10) perm([], [_G479, _G485, _G491|_G495]) ? creep
   Redo: (13) takeout(3, _G492, _G495) ? creep
   Call: (14) takeout(3, _G498, _G501) ? creep
   Exit: (14) takeout(3, [3|_G501], _G501) ? creep
   Exit: (13) takeout(3, [_G497, 3|_G501], [_G497|_G501]) ? creep
   Exit: (12) takeout(3, [_G491, _G497, 3|_G501], [_G491, _G497|_G501]) ? creep
   Exit: (11) takeout(3, [_G485, _G491, _G497, 3|_G501], [_G485, _G491, _G497|_G501]) ? creep

在第二种情况下：

X = [1, 2, 3] ;
   Redo: (8) takeout(1, _G451, [2, 3]) ? creep
   Call: (9) takeout(1, _G532, [3]) ? creep
   Exit: (9) takeout(1, [1, 3], [3]) ? creep
   Exit: (8) takeout(1, [2, 1, 3], [2, 3]) ? creep
   Exit: (7) perm([1, 2, 3], [2, 1, 3]) ? creep

因此，谓词枚举的顺序实际上很重要。在第一种情况下，您产生了许多具有未知值的状态。（尽可能）列出一张纸清单，运行trace并画出真正发生的事情，这将是一个好主意。

但简而言之，在第一种情况下，您会产生许多覆盖着takeout事实的未知变量，这些变量无法与perm.

于 2011-11-09T20:51:06.480 回答
0

Prolog 使用SLD 解析，因此子句中的子句顺序和文字顺序确实有所不同。基本上，引擎尝试通过以深度优先的方式从上到下搜索来解析子句标题。换句话说，在声明性语义之上还有一个过程语义。这种区别有时会让初学者感到困惑，但另一方面，它是 Prolog 真正成为一种编程语言（即图灵完备）的关键原因。

于 2012-02-07T23:02:30.797 回答
-1

your base case perm([],[]) needs to appear first, otherwise it will keep descending into the perm predicate until you run out of stack space. keep that in mind for future predicates too, its very important in prolog.

Also, you should probably switch up the order of perm & takeout in the other predicate.

于 2011-11-09T21:20:40.973 回答