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