prolog：列表中最大重复元素

Question

任何想法如何检索列表中最大重复元素。

即类似下面，

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

Answer 1

该解决方案对列表进行排序，给予元素依次出现 - 没有必要保持所有的元素，一旦他们以后不重复。

您的prolog解释器必须具有msort()功能，该功能对维护重复条目的列表进行排序。

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) 
    ). 

该复杂性是通常O(n log n)使用的排序，给出一次，排序后，遍历此列表只有一次，聚集要素，并保持最频繁的一个的轨道。

问候！

Answer 2

如果知道最大值是一个_我可以采取，如果这方面的一个_最大就是这样，你可以创建一个数组，大到_最大然后有一种方法，通过它可以找到O（n）时间中最重复的元素。

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) 

Answer 3

这是一个快速和肮脏的答案。我将问题限制在一组允许的元素中。工程，但需要阐述。

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). 

Answer 4

我喜欢这么多的关系Prolog的功率：

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. 

测试：

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

编辑和现在，更紧凑！

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