prolog: maximally repeated element in a list

问题:

Any ideas how to retrieve the maximally repeated element in a list.

i.e. something like below,

?- maxRepeated([1,2,7,3,6,1,2,2,3],M).
M = 2.

回答1:

This solution sorts the list, granting elements to appear sequentially -- there's no need to maintain all elements, once they're not repeating later.

Your prolog interpreter must have the function msort(), which sorts a list maintaining duplicated entries.

maxRepeated([], []).
maxRepeated(L, E) :-
    msort(L, [H|T]),
    maxRepeated(T, H, H, 1, 0, E).

maxRepeated([], H, _, C1, C2, H) :- C1 >= C2.
maxRepeated([], _, X, C1, C2, X) :- C1 < C2.

maxRepeated([H|T], H, LastF, C1, C2, E) :-
    maxRepeated(T, H, LastF, C1 + 1, C2, E).

maxRepeated([X|T], H, LastF, C1, C2, E) :-
    (
        C1 > C2
        ->  maxRepeated(T, X, H, 1, C1, E)
        ;   maxRepeated(T, X, LastF, 1, C2, E)
    ).

The complexity is given by the sort used, usually O(n log n), once, after the sort, the list is traversed only once, aggregating the elements and keeping track of the most frequent one.

Regards!

回答2:

I like so much the relational Prolog power:

maxRepeated(L, M) :-
    sort(L, S),
    maplist(count(L), S, C),
    keysort(C, [_-M|_Ms]).
count(L, S, I-S) :-
    aggregate(count, member(S, L), C), I is -C.

test:

?- maxRepeated([1,2,7,3,6,1,2,2,3],M).
M = 2.

edit and now, still more compact!

maxRepeated(L, M) :-
    setof(I-E, C^(aggregate(count, member(E, L), C), I is -C), [_-M|_]).

回答3:

If you know the max value that A_i can take and if this A_max is such that you can create an array as large as A_max then there is a method by which you can find the most repeated element in O(n) time.

int A[max+1]; // set all elements to 0
int S[n]; // Set S
for (i=0;i<n;i++) A[ S[i] ]++;

int m=0, num; // num is the number to be found
for (i=1;i<=max;i++)
  if (A[i] > m)
  {
    m = A[i];
    num = i;
  }
print (num)

回答4:

Here is a quick and dirty answer. I constrained the problem to a set of allowed elements. Works but needs elaboration.

maxRepeated([],_,Current,_,Current).
maxRepeated([H|T],L,Current,MaxCount,X) :-
    (
         count(L,H,N),
         N > MaxCount,
     maxRepeated(T,L,H,N,X) 
    )
    ;
    maxRepeated(T,L,Current,MaxCount,X).

count([],X,0).
count([X|T],X,Y):- count(T,X,Z), Y is 1+Z.
count([X1|T],X,Z):- X1\=X,count(T,X,Z).