2

如何检索列表中重复次数最多的元素的任何想法。

即如下所示，

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

4 回答 4

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|_]).
于 2012-12-02T22:02:30.007 回答
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)一次，在排序之后，列表只遍历一次，聚合元素并跟踪最频繁的元素。

问候！

于 2012-12-02T21:45:55.447 回答
0

如果您知道 A i可以取的最大值，并且如果此 A max可以创建一个与 A max一样大的数组，那么有一种方法可以在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)
于 2012-12-02T21:10:25.793 回答
0

这是一个快速而肮脏的答案。我将问题限制在一组允许的元素上。有效，但需要详细说明。

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).
于 2012-12-02T21:34:45.247 回答