프롤로그 - 시퀀스의 목록

Question

목록 L과 숫자 N을 얻고 N이 목록 L의 가장 긴 시퀀스의 길이 인 경우 참이됩니다. 예를 들어 :

?- ls([1,2,2,4,4,4,2,3,2],3). 
    true. 

?- ls([1,2,3,2,3,2,1,7,8],3). 
    false. 

이 들어 나는 내장 -

head([X|S],X). % head of the list 
ls([H|T],N) :- head(T,X),H=X, NN is N-1 , ls(T,NN) . % if the head equal to his following 
ls(_,0) :- !. % get seq in length N 
ls([H|T],N) :- head(T,X) , not(H=X) ,ls(T,N). % if the head doesn't equal to his following 

개념은 간단하다 - 그의 다음과 같 머리, 그렇다면, 꼬리를 계속하고 N을 감소되었는지 확인합니다.

나는 내 코드를 확인하고 그것을 잘 작동합니다 (예를 무시하는 N = 1) -

ls([1,2,2,4,4,4,2,3,2],3). 
true ; 
false . 

그러나 true 대답은 유한하지 않고 그 이후로 많은 대답은 나는 그것이 유한 돌아 만들 수있는 방법이있다 대답 ?

Answer 1

프롤로그와 마찬가지로 몇 가지 문제가 있습니다. 하나는 두 개의 인수가 인스턴스화 될 때만 술어가 작동한다는 것이고, 이는 Prolog에 실망입니다. 다른 하나는 스타일입니다. head/2은 실제로 [H|T] 이상을 추가하지 않습니다. 나는 또한이 알고리즘이 근본적으로 결함이 있다고 생각한다. 짐작할 수있는 길이의 복사본을 그대로 유지하지 않고리스트의 꼬리 부분에 더 이상 길이가없는 시퀀스가 ​​없다는 것을 확신 할 수 있다고 생각하지 않습니다. 다시 말해, 두 번째로 @Zakum이 지적한 바에 따르면 간단한 솔루션이 될 것이라고는 생각하지 않습니다.

이렇게하면 문제를 해결할 수 있습니다. 빈리스트의 기본 경우를 제외하고, 작업 sequence_length/2의 대부분이 루프에 위임 않습니다 이제

max(X, Y, X) :- X >= Y. 
max(X, Y, Y) :- Y > X. 

: 두 값의 최대 값을 얻기위한 첫 번째 도우미 술어

sequence_length([], 0). 
sequence_length([X|Xs], Length) :- 
    once(sequence_length_loop(X, Xs, 1, Length)). 

once/1으로 전화하면 단 하나의 답을 얻을 수 있습니다. 이렇게하면 술어가 순서가있는 목록을 유용하게 생성하지 못하도록하고 동시에 술어를 결정적으로 만드는 것을 막을 수 있습니다. (잘 배치 된 컷과 같은 효과가 있습니다).

루프의 기본 케이스 : 출력 파라미터에 어큐뮬레이터를 복사

sequence_length_loop(_, [], Length, Length). 

유도 케이스 1 : 우리는 동일한 값의 다른 복사본을 가지고있다. 축전지를 증가시키고 반복하십시오.

sequence_length_loop(X, [X|Xs], Acc, Length) :- 
    succ(Acc, Acc1), 
    sequence_length_loop(X, Xs, Acc1, Length). 

유도 성 사건 # 2 : 우리는 다른 값을 가지고 있습니다. 목록의 나머지 시퀀스 길이를 계산하십시오. 그것이 우리 누산기보다 큰 경우, 그것을 사용하십시오; 그렇지 않으면 축약기를 사용하십시오.

sequence_length_loop(X, [Y|Xs], Acc, Length) :- 
    X \= Y, 
    sequence_length([Y|Xs], LengthRemaining), 
    max(Acc, LengthRemaining, Length). 

이렇게하면이 문제에 접근하게됩니다. 나는 그것이 당신에게 도움이되는지 아닌지 모르지만, 당신이 그걸로 무엇인가를 모을 수 있기를 바랍니다.

Answer 2

마지막 규칙에 휴식 시간을 추가하는 것은 어떻습니까?

head([X|S],X). % head of the list 
ls([H|T],N) :- head(T,X),H=X, NN is N-1 , ls(T,NN) . % if the head equal to his following 
ls(_,0) :- !.           % get seq in length N 
ls([H|T],N) :- head(T,X) , not(H=X) ,ls(T,N),!.   % if the head doesn't equal to his following 

필자는 Prolog 전문가가 아니지만 작동합니다.

// 편집 : btw. 시도해보십시오.

14 ?- ls([1,2,2,4,4,4,2,3,2],2). 
true ; 
false. 

N은 가장 긴 시퀀스인지 확인하지 않습니다. 또는 요구 사항이 잘못 되었습니까?

Answer 3

코드에 지정된 길이의 요소 시퀀스가 ​​적어도 목록에 있는지 확인하고 있습니다. 목록을 방문하는 동안 검색 상태를 유지하려면 더 많은 논의가 필요합니다.

ls([E|Es], L) :- ls(E, 1, Es, L). 

ls(X, N, [Y|Ys], L) :- 
    ( X = Y 
    -> M is N+1, 
    ls(X, M, Ys, L) 
    ; ls(Y, 1, Ys, M), 
    (M > N -> L = M ; L = N) 
). 
ls(_, N, [], N).