4

我正在尝试在 Prolog 中创建此功能：

% Signature: circleList(L1, L2)/2
% Purpose: L2 is a "circled" L1 list.
% Precondition: L1 is fully instantiated.
% Examples:
% ?- circleList([2, 3, 4, 5], X).
% X = [2, 3, 4, 5];
% X = [3, 4, 5, 2];
% X = [4, 5, 2, 3];
% X = [5, 2, 3, 4];
% false.

所以我这样做了：

circleList([],[]).
circleList(X,X).
circleList([H|T],R):- append(T,[H],S), circleList(S,R).

但输出是这样的：

X = [2, 3, 4, 5] ;
X = [3, 4, 5, 2] ;
X = [4, 5, 2, 3] ;
X = [5, 2, 3, 4] ;
X = [2, 3, 4, 5] ;
X = [3, 4, 5, 2] ;
X = [4, 5, 2, 3] ;
X = [5, 2, 3, 4] ;
X = [2, 3, 4, 5] ;
X = [3, 4, 5, 2] 
and so on...

这很好，但我想在我第一次做所有的可能性后让它停下来。

我能做些什么？

4

3 回答 3

3

您的谓词需要另一个参数。一种选择是使用列表中的元素，直到剩下[].

circleList([Head|Tail],CL):-
    circleList(Tail,[Head],CL).

circleList([],L,L).
circleList([Head|Tail], Rest, CL):-
    append(Rest, [Head], NewRest),
    circleList(Tail, NewRest, CL).
circleList([Head|Tail], Rest, CL):-
    append([Head|Tail], Rest,CL).

我看到的另一个选项是使用length/2.

circleList([],[]).
circleList(List,CL):-
    length(List, N),
    circleList(List,N,CL).

circleList(_,0,_):-!, fail.
circleList(List,_,List).
circleList([Head|Tail], N, CL):-
    append(Tail, [Head], NewList),
    N1 is N - 1,
    circleList(NewList, N1, CL).
于 2014-06-10T14:08:29.823 回答
3

您可以简单地以不同的方式表述问题：

rotatelist([], []).
rotatelist(Xs, Ys) :-
   Xs = [_|_],
   Ys = [_|_],
   same_length(Xs, Ys), % avoid non-termination
   Bs = [_|_],          % avoid redundant answers
   append(As,Bs,Xs),
   append(Bs,As,Ys).

same_length([], []).
same_length([_E|Es], [_F|Fs]) :-
   same_length(Es, Fs).

但是，如果您的意思是明确停止；好吧，这很容易被证明是不正确的。事实上，我看不到在这里如何使用剪切的自然方式。

但是，您可以像这样限制递归的数量：

circleList2(Xs, Ys) :-
   same_length(Xs, Ys),
   circleList2(Xs, Ys, Xs).

circleList2(X,X, _).
circleList2([H|T],R, [_|L]):-
   L = [_|_],
   append(T,[H],S),
   circleList2(S,R, L).

因此，这本质上是您的程序，带有一个用于限制递归次数的附加参数。以这种方式限制递归通常用于实现所谓的迭代深化算法。然而，在这种情况下，我们只有一个深度界限。不需要额外的迭代。

于 2014-06-10T14:08:48.047 回答
2

这是一个更简单的解决方案，具有更弱的终止特性。另一方面，您说第一个参数是“完全实例化的”。您能否快速为要“完全实例化”的参数生成测试？我假设不是。正是由于这个原因，这样的假设导致了如此多的错误。首先，程序员只是假设参数将被“完全实例化”，然后他们忘记了他们的假设......

circleList3(Xs, Ys) :-
   append(As, Bs, Xs),
   append(Bs, As, Ys),
   ( As = [] ; As = [_|_], Bs = [_|_] ).

此版本现在不再终止于circleList3(Xs, []). 要了解为什么会这样，我将使用一个，即我将false在程序中添加。如果剩余部分仍然没有终止，那么一个问题在于可见部分。

?- circleList3(Xs, []), false。
/* 循环 */

circleList3(Xs, Ys) :-
   append(As, Bs, Xs), false, 
   append(Bs, As, Ys) ,
    ( As = [] ; As = [_|_], Bs = [_|_] )。

这个失败切片不会终止，因为第一个目标是用 3 个未实例化的参数调用的。获得此终止的唯一帮助是Ys，但没有人对此感兴趣！

我们现在可以交换两个目标append/3，使这个片段终止，但是，其他查询不会终止......

于 2014-06-11T11:03:48.737 回答