我想计算列表中元素的出现次数 [英] I want to count the occurrences of an element in a list

问题描述

我想计算列表中某个元素的出现次数，如果有一个元素，则谓词unique将为true，否则为false。但是，如果元素多次出现，Prolog会发现它为真。我不知道该怎么做...

I want to count the occurrences of an element in a list, and if there is one then the predicate unique would be true, else false. However, if the element occurs more than once, Prolog finds it true. I don't know what to do...

count([], X, 0).
count([X|T], X, Y) :- count(T, X, Z), Y is 1+Z, write(Z).
count([_|T], X, Z) :- count(T, X, Z).

unique(St, [Y|RestList]) :- count([Y|RestList], St, N), N =:= 1.

推荐答案

解决方案的工作原理是第一个参数是一个基本列表。在其他一些情况下，它是不正确的：

The solution works as far as the first argument is a ground list. In some other cases, it is incorrect:

?- count([E], a, 0).
false.

这里我们要求

长度为1的列表的元素 E 如何显示为包含0个 a ？

How must the element E of a list of length 1 look like such that the list contains 0 occurences of a?

事实上有这样的答案，比如 E = b 或 E = c ：

And in fact there are answers to this, like E = b or E = c:

?- count([b],a,0).
true.

?- count([c],a,0).
true.

因为这个原因，Prolog的回答是不完整。它应该说，是的。但是如何？

For this reason Prolog's answer was incomplete. It should have said, yes. But how?

count([], _, 0).
count([E|Es], F, N0) :-
   count(Es, F, N1),
   if_(E = F, D = 1, D = 0),
   N0 is N1+D.

这采用的 if_ / 3 和 （= ）/ 3 。

This uses if_/3 and (=)/3.

?- length(Xs, I), count_dif(Xs, a, N).
   Xs = [],
   I = N, N = 0
;  Xs = [a],
   I = N, N = 1
;  Xs = [_A],
   I = 1,
   N = 0,
   dif(_A, a)
;  Xs = [a, a],
   I = N, N = 2
;  Xs = [_A, a],
   I = 2,
   N = 1,
   dif(_A, a) ;
   Xs = [a, _A],
   I = 2,
   N = 1,
   dif(_A, a) ;
   Xs = [_A, _B],
   I = 2,
   N = 0,
   dif(_A, a),
   dif(_B, a)
...

为了进一步改进这一点，我们可以使用 （clpfd），因为它是提供SICStus，YAP和SWI

To further improve this, we might use library(clpfd) as it is available in SICStus, YAP, and SWI.

:- use_module(library(clpfd)).

count([], _, 0).
count([E|Es], F, N0) :-
   N0 #>= 0,
   if_(E = F, D = 1, D = 0),
   N0 #= N1+D,
   count(Es, F, N1).

现在甚至以下终止：

?- count([a,a|_], a, 1).
false.

?- N #< 2, count([a,a|_], a, N).
false.

这篇关于我想计算列表中元素的出现次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！