2

こんにちは、リストを指定して、次のようにリスト内の連続する各要素の出現をカウントするプログラムをPrologで作成しようとしています:

count(1,[1,1,1,2,2,2,3,1,1],0,X)

結果はX=[ [1,3],[2,3],[3,1][1,2] ] 別名、各サブリストは[element,occurrences]

私の場合、基本ケースに問題があると思いますが、解決できません。手伝って頂けますか？

%append an element to a list
append([ ],Y,Y).
append([X|Xs],Ys,[X|Zs]):-append(Xs,Ys,Zs).

%c is the counter beginning with 0 
count(_,[],_,[]).
count(X,[X],C,[L]):-count(X,[],C,[L|[X,C]]).

%increase counter
count(X,[X|Tail],C,L):-Z is C+1,count(X,Tail,Z,L).
count(X,[Head|Tail],C,[L]):-append(L,[X,C],NL),count(Head,Tail,1,NL).
4

5 に答える 5

3

私たちはあなたの問題に取り組み、を維持することができます!

以下では、質問で使用したリストを としますXs。[1,1,1,2,2,2,3,1,1]

最初に、 のすべてのリストにから取得した等しい要素のみが含まれるようXsに、リストのリストにマップします。具体化された不等式述語と連携してメタ述語を使用することにより、これを行います。YssYsYssXssplitlistIfAdj/3dif/3

?- Xs = [1,1,1,2,2,2,3,1,1], splitlistIfAdj(dif,Xs,Yss).
Xs  = [ 1,1,1,  2,2,2,  3,  1,1 ],
Yss = [[1,1,1],[2,2,2],[3],[1,1]].

次に、リストのリストを にマップしYssますZss。の各項目 Zssの形式は[Element,Amount]です。上記のクエリの答えを見ると、 to 、to 、to 、toにマップするだけでよいことがわかります。まさにそれを行います：[1,1,1][1,3][2,2,2][2,3][3][3,1][1,1][1,2]run_pair/2

run_pair(Ys,[Element,Amount]) :-
   Ys = [Element|_],
   length(Ys,Amount).

meta-predicate の助けを借りて、 のrun_pair/2すべてのアイテムをマップするために使用しましょう:Yssmaplist/3

?- Yss = [[1,1,1],[2,2,2],[3],[1,1]], maplist(run_pair,Yss,Zss).
Yss = [[ 1 , 1 , 1 ],[ 2 , 2 , 2 ],[ 3 ] ,[ 1 , 1 ]],
Zss = [[ 1 , 3 ], [ 2 , 3 ], [ 3 , 1 ],[ 1 , 2 ]].

終わり！すべてをまとめる時間：

count(Xs,Zss) :-
   splitlistIfAdj(dif,Xs,Yss),
   maplist(run_pair,Yss,Zss).

上記のクエリがまだ機能するかどうか見てみましょう:)

?- count([1,1,1,2,2,2,3,1,1],Zss).
Zss = [[1,3],[2,3],[3,1],[1,2]].      % succeeds deterministically

の実装count/2はmonotoneであるため、根拠のない用語を扱っている場合でも、論理的に正しい答えが得られます。実際に見てみましょう！

?- Xs = [A,B,C,D], count(Xs,Zss).
Xs = [D,D,D,D],     A=B,      B=C ,     C=D , Zss = [                  [D,4]] ;
Xs = [C,C,C,D],     A=B,      B=C , dif(C,D), Zss = [            [C,3],[D,1]] ;
Xs = [B,B,D,D],     A=B,  dif(B,C),     C=D , Zss = [      [B,2],      [D,2]] ;
Xs = [B,B,C,D],     A=B,  dif(B,C), dif(C,D), Zss = [      [B,2],[C,1],[D,1]] ;
Xs = [A,D,D,D], dif(A,B),     B=C ,     C=D , Zss = [[A,1],            [D,3]] ;
Xs = [A,C,C,D], dif(A,B),     B=C , dif(C,D), Zss = [[A,1],      [C,2],[D,1]] ;
Xs = [A,B,D,D], dif(A,B), dif(B,C),     C=D , Zss = [[A,1],[B,1],      [D,2]] ;
Xs = [A,B,C,D], dif(A,B), dif(B,C), dif(C,D), Zss = [[A,1],[B,1],[C,1],[D,1]].
于 2015-05-16T18:58:04.867 に答える
2

4 つの引数を持つ述語を持つ 2 つのリスト間の関係を述べているのはなぜですか? 一歩一歩進んでいきましょう。

空のリストは空のリストを与え、カウントされた要素はインクリメントされます。そうでない場合は、カウントを開始します...

count([],[]).
count([X|T],[[X,C1]|R]) :- count(T,[[X,C]|R]), !, C1 is C+1.
count([X|T],[[X,1]|R]) :- count(T,R).

?- count([1,1,1,2,2,2,3,1,1],R).
R = [[1, 3], [2, 3], [3, 1], [1, 2]].

とても簡単です (もちろん、 X=[ [1,3],[2,3], [1,3] [1,2] ] と仮定すると、それはタイプミスです ...)

于 2014-11-20T21:40:27.987 に答える
0

別の解決策 (末尾再帰) は次のとおりです。

run_length_encode( Xs , Ys ) :- % to find the run length encoding of a list ,
  rle( Xs , 1 , Ys ) .          % - just invoke the helper

rle( []       , _ , []    ) .     % the run length encoding of the empty list is the empty list
rle( [A]      , N , [X:N] ) .     % A list of length 1 terminates the run: move the run length to the result
rle( [A,A|Xs] , N , Ys    ) :-    % otherwise, if the run is still going
  N1 is N+1 ,                     % - increment the count, 
  rle( [A|Xs] , N1 , Ys )         % - and recurse down
  .                               %
rle( [A,B|Xs] , N , [A:N|Ys] ) :- % otherwise, if the run has ended
  A \= B ,                        % - we have a break
  rle( [B|Xs] , 1 , Ys )          % - add the completed run length to the result and recurse down
  .                               %
于 2014-11-21T01:06:49.007 に答える