リスト内で最大に繰り返される要素を取得する方法のアイデア。
つまり、以下のようなもの、
?- maxRepeated([1,2,7,3,6,1,2,2,3],M).
M = 2.
リスト内で最大に繰り返される要素を取得する方法のアイデア。
つまり、以下のようなもの、
?- maxRepeated([1,2,7,3,6,1,2,2,3],M).
M = 2.
私はリレーショナル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|_]).
このソリューションは、リストを並べ替えて、要素が順番に表示されるようにします。後で繰り返されない限り、すべての要素を維持する必要はありません。
プロローグインタプリタには、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回だけトラバースされ、要素を集約し、最も頻繁なものを追跡します。
よろしく!
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)
ここに簡単で汚い答えがあります。問題を許可された要素のセットに限定しました。動作しますが、詳細が必要です。
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).