list - 计算 Prolog 中数字的连续出现次数

Question

您好，我正在尝试在 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).

Answer 1

我们可以解决您的问题并保留 logical-purity !

下面让Xs是[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] 。看看上面查询的答案，我们发现我们需要做的就是映射 [<b>1</b>,<b>1</b>,<b>1</b>]至[<b>1</b>,<i>3</i>] , [<b>2</b>,<b>2</b>,<b>2</b>]至[<b>2</b>,<i>3</i>] , [<b>3</b>]至[<b>3</b>,<i>1</i>] ，和[<b>1</b>,<b>1</b>]至[<b>1</b>,<i>2</i>] 。 run_pair/2正是这样做的:

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

让我们使用run_pair/2映射 Yss 的每一项，借助元谓词 maplist/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]].

Done! Time to put it all together:

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