Which list item is the most common

Question

I'm trying to find the most common list item common([b,a,a,a,c,d,b,f,s,f,s,f,s,f,s,f,f],R) so the result should be R=f, I was thinking if we take the list , go to the end of the list take el=b ,num1=1 then go back to the beginning and compare if b=b ,num1=num1+1 else a!=b then if num2=num2+1 , num1>num2 recursion else el=a or something like this, but i had some difficulty transforming it into Prolog.

insert_sort sorts the list , but for some interesting reason if i use las(X,Y) (I override the original last/2 ) I get 4-a if I use last(X,Y) i get just a...

most_common([X|Y],J):-
    insert_sort([X|Y],[R|Rs]),             
    count_runs([R|Rs],G),
    las(G,J).

las([N-Y],Y).
las([_|T],Y):- las(T,Y).
las([_|Tail], Y) :- las(Tail, Y).

insert_sort(List,Sorted):-
   i_sort(List,[],Sorted).

i_sort([],Acc,Acc).
i_sort([H|T],Acc,Sorted):- 
    insert(H,Acc,NAcc),
    i_sort(T,NAcc,Sorted).

insert(X,[],[X]).     
insert(X,[Y|T],[Y|NT]):- X @> Y, insert(X,T,NT).
insert(X,[Y|T],[X,Y|T]):- X @=< Y.

Answer 1

Based on Prolog lambdas, we use the meta-predicates tcount/3 and reduce/3, as well as the reified term equality predicate (=)/3:

:- use_module(library(lambda)).

mostcommon_in(E,Xs) :-
   tcount(=(E),Xs,M),
   maplist(Xs+\X^N^(tcount(=(X),Xs,N)),Xs,Counts),
   reduce(\C0^C1^C^(C is max(C0,C1)),Counts,M).

Sample query:

?- mostcommon_in(X,[a,b,c,d,a,b,c,a,b]).
X = a ;
X = b ;
false.

Note that this is monotone (unlike it's earlier quick-hack version). Look!

?- mostcommon_in(X,[A,B,C,D,A,B,C,A,B]), A=a,B=b,C=c,D=d.
X = a, A = a, B = b, C = c, D = d ;
X = b, A = a, B = b, C = c, D = d ;
false.

Answer 2

Preserve logical-purity by using list_counts/2 for defining mostcommonitem_in/2 as follows:

mostcommonitem_in(E,Xs) :-
   list_counts(Xs,Cs),                      % tag items with multiplicity
   maplist(\ (X-N)^(M-X)^(M is -N),Cs,Ps),  % prepare keysorting
   keysort(Ps,[Max-_|_]),                   % sort ascending by negated count
   member(Max-E,Ps).                        % pick most common ones

Let's run a query!

?- mostcommonitem_in(X,[a,b,c,d,a,b,c,a,b]).
X = a ;
X = b ;
false.                                % OK

But, is it still monotone?

?- mostcommonitem_in(X,[A,B,C,D,A,B,C,A,B]), A=a,B=b,C=c,D=d.
X = A, A = a, B = b, C = c, D = d ;
X = B, B = b, A = a, C = c, D = d ;
false.                                % OK: monotone

Got speed? (compared to the pure answer I showed in my previous answer to this question)

% OLD
?- length(Xs,5), time(findall(t,mostcommon_in(E,Xs),Ts)), length(Ts,N_sols).
% 854,636 inferences,    0.115 CPU in 0.115 seconds (100% CPU, 7447635 Lips)
N_sols = 71,   Xs = [_,_,_,_,_],     Ts = [t,t,t|...].    
?- length(Xs,6), time(findall(t,mostcommon_in(E,Xs),Ts)), length(Ts,N_sols).
% 4,407,975 inferences,  0.449 CPU in 0.449 seconds (100% CPU, 9813808 Lips)
N_sols = 293,  Xs = [_,_,_,_,_,_],   Ts = [t,t,t|...].
?- length(Xs,7), time(findall(t,mostcommon_in(E,Xs),Ts)), length(Ts,N_sols).
% 24,240,240 inferences, 2.385 CPU in 2.384 seconds (100% CPU, 10162591 Lips)
N_sols = 1268, Xs = [_,_,_,_,_,_,_], Ts = [t,t,t|...].

% NEW
?- length(Xs,5), time(findall(t,mostcommonitem_in(E,Xs),Ts)), length(Ts,N_sols).
% 4,031 inferences, 0.001 CPU in  0.002 seconds (93% CPU, 2785423 Lips)
N_sols = 71,   Xs = [_,_,_,_,_],     Ts = [t,t,t|...].    
?- length(Xs,6), time(findall(t,mostcommonitem_in(E,Xs),Ts)), length(Ts,N_sols).
% 17,632 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 9194323 Lips)
N_sols = 293,  Xs = [_,_,_,_,_,_],   Ts = [t,t,t|...].    
?- length(Xs,7), time(findall(t,mostcommonitem_in(E,Xs),Ts)), length(Ts,N_sols).
% 82,263 inferences, 0.023 CPU in 0.023 seconds (100% CPU, 3540609 Lips)
N_sols = 1268, Xs = [_,_,_,_,_,_,_], Ts = [t,t,t|...].

Answer 3

This looks like homework, so I'm not going to give you a full answer, but will suggest how you could solve it in one particular way, which isn't necessarily the best way:

• Sort the list into sorted order (by standard order of terms if this is good enough): look at sort/2 routines. e.g., [b,a,a,a,c,d,b] becomes [a,a,a,b,b,c,d].

• Take the sorted list and count the size of 'runs', perhaps to convert [a,a,a,b,b,c,d] into [3-a,2-b,1-c,1-d] (where -/2 is simply another term). e.g., consider the following code:

---

count_runs([E|Es], C) :-
      % defer to count_runs/3 with an initial count of element E
    count_runs(Es, 1-E, C).

  % return the final count for Y elements if none remain (base case)
count_runs([], N-Y, [N-Y]). 

count_runs([X|Es], N-Y, [N-Y|Rest]) :-
      % if X is not equal to Y, record the count and continue next run
    X \== Y, !,  
    count_runs([X|Es], Rest).

count_runs([_X|Es], N-Y, Rest) :-
      % else X equals Y; increment the counter and continue
    NPlusOne is N + 1,
    count_runs(Es, NPlusOne-Y, Rest).

---

• Perform something like keysort/2 to order the terms by the value of their keys (i.e., the numbers which are the counts, turning [3-a,2-b,1-c,1-d] into [1-c,1-d,2-b,3-a]). Then, the most-occurring elements of the list are the values at the end of the list with the same key value (i.e., here, this is the a in the last term 3-a). In general, they may be more than one element that occurs the most (equally with another).

Good luck.

Answer 4

I could give you a high-level answer: You could sort the list and then it's relatively easy to count the items, one after another, and update what so far is the most common item.