Repeated elements in a list in Prolog

Question

I would like to find a method to find the most repeated element in a list if two elements repeat the same number of times. I want the predicate to be a list that contains both elements. How can I do that?

Sample queries and expected answers:

?- maxRepeated([1,3,3,4,2,2],X).
X = [3,2].

% common case: there is one element that is the most repeated
?- maxRepeated([1,3,3,3,3,4,2,2],X).
X = [3].

% all elements repeat the same number of times
?- maxRepeated([1,3,4,2],X).
X = [1,3,4,2].

I have the same problem with the less repeated element.

Answer 1

The predicate mostcommonitems_in/2 (to be presented in this answer) bears more than a little resemblance to mostcommonitem_in/2, defined in one of my previous answers.

In the following we use list_counts/2, Prolog lambdas, foldl/4, tchoose/3, and (=)/3:

:- use_module(library(lambda)).

mostcommonitems_in(Ms,Xs) :-
   list_counts(Xs,Cs),
   foldl(\ (_-N)^M0^M1^(M1 is max(M0,N)),Cs,0,M),
   tchoose(\ (E-N)^E^(N=M), Cs,Ms).

Let's run some queries!

First, the three queries given by the OP:

?- mostcommonitems_in(Xs,[1,3,3,4,2,2]).
Xs = [3,2].

?- mostcommonitems_in(Xs,[1,3,3,3,3,4,2,2]).
Xs = [3].

?- mostcommonitems_in(Xs,[1,3,4,2]).
Xs = [1,3,4,2].

Alright! Some more ground queries---hat tip to @lurker and @rpax:

?- mostcommonitems_in(Xs,[1,3,2,1,3,3,1,4,1]).
Xs = [1].

?- mostcommonitems_in(Xs,[1,3,3,4,3,2]).
Xs = [3].

?- mostcommonitems_in(Xs,[1,2,3,4,5,6]).
Xs = [1,2,3,4,5,6].

?- mostcommonitems_in(Xs,[1,3,3,4,2,3,2,2]).
Xs = [3,2].

OK! How about three items each of which occurs exactly three times in the list?

?- mostcommonitems_in(Xs,[a,b,c,a,b,c,a,b,c,x,d,e]).
Xs = [a,b,c].                                          % works as expected 

How about the following somewhat more general query?

?- mostcommonitems_in(Xs,[A,B,C]).
  Xs = [C]    ,     A=B           ,     B=C
; Xs = [B]    ,     A=B           , dif(B,C)
; Xs = [C]    ,               A=C , dif(B,C)
; Xs = [C]    ,           dif(A,C),     B=C
; Xs = [A,B,C], dif(A,B), dif(A,C), dif(B,C).

Above query breaks almost all impure codes... Our Prolog code is pure, so we're good to go!

Answer 2

I don't know too much about prolog, and probably there's a way to do this better, but here's a working solution: (SWI prolog)

%List of tuples, keeps track of the number of repetitions.
modify([],X,[(X,1)]).
modify([(X,Y)|Xs],X,[(X,K)|Xs]):- K is Y+1.
modify([(Z,Y)|Xs],X,[(Z,Y)|K]):- Z =\= X, modify(Xs,X,K).

highest((X1,Y1),(_,Y2),(X1,Y1)):- Y1 >= Y2.
highest((_,Y1),(X2,Y2),(X2,Y2)):- Y2 > Y1.

maxR([X],X).
maxR([X|Xs],K):- maxR(Xs,Z),highest(X,Z,K).

rep([],R,R).
rep([X|Xs],R,R1):-modify(R,X,R2),rep(Xs,R2,R1).

maxRepeated(X,R):- rep(X,[],K),maxR(K,R).


?- maxRepeated([1,3,3,4,3,2] ,X).
X = (3, 3) .

?- maxRepeated([1,2,3,4,5,6] ,X).
X = (1, 1) .

The less repeated element is analogous.

I think that is better to use tuples in this case, but changing the result into a list shouldn't be a problem.

Answer 3

There is my solution on Visual Prolog:

domains
value=integer
tuple=t(value,integer)
list=value*
tuples=tuple*

predicates
modify(tuples,value,tuples)
highest(tuple,tuple,tuple)
maxR(tuples,integer,integer)
maxR(tuples,integer)
rep(list,tuples,tuples)
maxRepeated(list,list)
filter(tuples,integer,list)

clauses
modify([],X,[t(X,1)]):- !.
modify([t(X,Y)|Xs],X,[t(X,K)|Xs]):- K = Y+1, !.
modify([t(Z,Y)|Xs],X,[t(Z,Y)|K]):- Z <> X, modify(Xs,X,K).

highest(t(X1,Y1),t(_,Y2),t(X1,Y1)):- Y1 >= Y2, !.
highest(t(_,Y1),t(X2,Y2),t(X2,Y2)):- Y2 > Y1.

maxR([],R,R):- !.
maxR([t(_,K)|Xs],Rs,R):- K>Rs,!, maxR(Xs,K,R).
maxR([_|Xs],Rs,R):- maxR(Xs,Rs,R).
maxR(X,R):- maxR(X,0,R).

rep([],R,R).
rep([X|Xs],R,R1):-modify(R,X,R2),rep(Xs,R2,R1).

filter([],_,[]):-!.
filter([t(X,K)|Xs],K,[X|FXs]):- !, filter(Xs,K,FXs).
filter([_|Xs],K,FXs):- filter(Xs,K,FXs).

maxRepeated(X,RL):- rep(X,[],Reps),maxR(Reps,K),filter(Reps,K,RL).

goal
maxRepeated([1,3,3,4,2,3,2,2] ,X),
maxRepeated([1,2,3,4,5,6] ,Y).