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

我们可以解决您的问题并保持！

在下面的 let Xsbe 中[1,1,1,2,2,2,3,1,1]，您在问题中使用的列表。

首先，我们映射Xs到一个列表列表，Yss这样每个列表Ys中的每个列表Yss都只包含来自 的相等元素Xs。我们通过将元谓词splitlistIfAdj/3与具体化的不等式谓词结合使用来做到这一点dif/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]。查看上述查询的答案，我们看到我们需要做的就是映射到、到、到和到。正是这样做的：[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是单调的，即使在使用非基本术语时，我们也会得到逻辑上合理的答案。让我们看看实际情况！

?- 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 个参数的谓词来说明两个列表之间的关系？让我们一步一步地尝试。

一个空列表给出一个空列表，计数的元素会增加，否则，开始计数......

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 回答
2

这是基于进行游程编码的另一种尝试！

:- 使用模块（库（clpfd））。

基于if_/3和(=)/3，我们定义list_rle/2：

list_rle([],[])。
list_rle([X|Xs],[N*X|Ps]) :-
   list_count_prev_runs(Xs,N,X,Ps)。

list_count_prev_runs(Es,N,X,Ps) :-
   N #> 0,
   N #= N0+1,
   list_count_prev_runs_(Es,N0,X,Ps)。

list_count_prev_runs_([],0,_,[])。
list_count_prev_runs_([E|Es],N,X,Ps0) :-
   if_(X=E,
       list_count_prev_runs(Es,N,X,Ps0),
       (N = 0, Ps0 = [M*E|Ps], list_count_prev_runs(Es,M,E,Ps)))。

示例查询：

  • 编码/解码#1

    ?- list_rle([a,a,b,c,c,c,d,e,e],Ys)。
Ys = [2*a,1*b,3*c,1*d,2*e]。

?- list_rle(Xs,[2*a,1*b,3*c,1*d,2*e])。
  Xs = [a,a,b,c,c,c,d,e,e]
; 错误的。

  • 编码/解码#2

    ?- dif(A,B),dif(B,C),dif(C,D),dif(D,E), list_rle([A,A,B,C,C,C,D,E,E ]，是）。
Ys = [2*A,1*B,3*C,1*D,2*E]，dif(A,B)，dif(B,C)，dif(C,D)，dif(D,E ）。

?- list_rle(Xs,[2*A,1*B,3*C,1*D,2*E])。
  Xs = [A,A,B,C,C,C,D,E,E], dif(A,B), dif(B,C), dif(C,D), dif(D,E)
; 错误的。

  • 更一般的东西怎么样？

    ?- list_rle([A,B,C,D],Xs)。
  Xs = [4*A]，A=B，B=C，C=D
; Xs = [3*A, 1*D], A=B, B=C, dif(C,D)
; Xs = [2*A, 2*C], A=B, dif(B,C), C=D
; Xs = [2*A, 1*C,1*D], A=B , dif(B,C), dif(C,D)
; Xs = [1*A,3*B], dif(A,B), B=C, C=D
; Xs = [1*A,2*B, 1*D], dif(A,B), B=C , dif(C,D)
; Xs = [1*A,1*B,2*C]，dif(A,B)，dif(B,C)，C=D   
; Xs = [1*A,1*B,1*C,1*D]，dif(A,B)，dif(B,C)，dif(C,D)。
于 2015-10-16T22:18:22.200 回答
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 回答
0

如果我们跳过“is”的使用，我们可以有如下解决方案：

precondition(Clause):-
  Clause =.. [_|ARGS],
  ( maplist(var,ARGS) -> true; Clause ).

count( [], [] ).

count( [X], [(X,1)] ) :- !.

count( [H|Q], [(H,1),(HR,NR)|QR] ) :-
   count( Q, [(HR,NR)|QR] ),
   H \= HR,
   !.

count( [H|Q], [(H,NR)|QR] ) :-
   precondition( succ(N,NR) ),
   count( Q, [(H,N)|QR] ), 
   succ(N,NR).

这不仅允许通常的查询：

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

但也是相反的：

[debug]  ?- count(X, [ (1, 3), (2, 3), (3, 1), (1, 2)] ).
X = [1, 1, 1, 2, 2, 2, 3, 1, 1].
于 2015-05-21T14:13:08.947 回答