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

このソリューションは、リストを並べ替えて、要素が順番に表示されるようにします。後で繰り返されない限り、すべての要素を維持する必要はありません。

プロローグインタプリタには、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)、ソート後、リストは1回だけトラバースされ、要素を集約し、最も頻繁なものを追跡します。

よろしく!

于 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 に答える