Re: Count lists elements

We should be able to solve this one cleanly without using sort, assert
and retract, or a constraints library, or any such thing! Keep it
simple.

We want to solve, e.g.:
:- most_often([a,b,c,a,v,s,a,b,t,a], K).

in other words,
:- most_often(Ks, K).

Let's say that's a wrapping for something even more useful:

most_often(Ks, K) :- most_often(Ks, K, _).

where the last slot returns "how many" of the most-common K in Ks
(which in the above case is irrelevant).

Taking the problem apart top-down, we can see that by"most_often", what
we mean is, by definition:

most_often(Ks, K, N) :- count(Ks, K, N), not (count(Ks, _, N1), N1 >
N).

And obviously,

count([], _, 0).
count([K|Ks], K, N1) :- count(Ks, K, N), N1 is N+1.
count([K|Ks], K1, N) :- K <> K1, count(Ks, K1, N).


That's not by any means the most processor-efficient solution, but it's
clear that it meets the specification, and it only takes five lines!
(And unless you're dealing with a HUGE list or massive recursion into
this predicate, who cares?) To reiterate:

most_often(Ks, K) :- most_often(Ks, K, _).

most_often(Ks, K, N) :- count(Ks, K, N), not (count(Ks, _, N1), N1 >
N).

count([], _, 0).
count([K|Ks], K, N1) :- count(Ks, K, N), N1 is N+1.
count([K|Ks], K1, N) :- K <> K1, count(Ks, K1, N).

Note that if you retry the goal most_often() it will find out if there
are any other answers that are just as good as the first match. That
is, it will look for a match for any other elements that happen to be
just as common as (one of?) the most-common one(s) it already found.
As it is, it will also return redundant answers, once for each time
such an element is found in the list. But wha'd'ya want in five lines
(four really) :^) .


We could make this approach a little more efficient, but at the expense
of some brevity and clarity, by giving up on the second count once it
gets too big:

most_often(Ks, K) :- most_often(Ks, K, _).

most_often(Ks, K, N) :- count(Ks, K, N), N1 is N+1, not count_to(Ks, _,
N1).

count([], _, 0).
count([K|Ks], K, N1) :- count(Ks, K, N), N1 is N+1.
count([K|Ks], K1, N) :- K <> K1, count(Ks, K1, N).

count_to([], _, 0).
count_to([K|Ks], K, N) :- N > 0, N_1 is N-1, count_to(Ks, K, N).
count_to([K|Ks], K1, N) :- K <> K1, count_to(Ks, K1, N).

(Here "count_to" is given a predetermined number to count to, and it
attempts to find some K that has AT LEAST that many copies in the list,
quitting as soon as it finds one (or fails).)
-- Glenn


Rapolas@xxxxxxxxx wrote:
Hi all,
I have a problem, I need to write a program, which finds the element in
a list which repeats most often time. Lets say, I have such query:
?- most_often([a,b,c,a,v,s,a,b,t,a], K).
K = a.

I tried several ways, but no luck... Can anybody help me?

.