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

述語には別の引数が必要です。1 つのオプションは、リストがなくなるまでリスト内の要素を消費することです[]。

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

したがって、これは本質的に、再帰の数を制限するために使用される 1 つの追加の引数を持つプログラムです。このような方法で再帰を制限することは、いわゆる反復深化アルゴリズムを実装するために一般的に使用されます。ただし、この場合、単一の深さの境界がありました。余分な反復は必要ありませんでした。

于 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ですが、誰もそれに興味を持っていません!

このフラグメントを終了させる2 つの目標を交換できますappend/3が、その後、他のクエリは終了しません...

于 2014-06-11T11:03:48.737 に答える