prolog:列表中最大重复的元素 [英] prolog: maximally repeated element in a list

问题描述

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

Any ideas how to retrieve the maximally repeated element in a list.

即像下面这样，

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

推荐答案

此解决方案对列表进行排序，允许元素按顺序出现 -- 无需维护所有元素，一旦它们以后不再重复.

This solution sorts the list, granting elements to appear sequentially -- there's no need to maintain all elements, once they're not repeating later.

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

Your prolog interpreter must have the function msort(), which sorts a list maintaining duplicated entries.

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)，一次，排序后，列表只遍历一次，聚合元素并跟踪最频繁的一个.

The complexity is given by the sort used, usually O(n log n), once, after the sort, the list is traversed only once, aggregating the elements and keeping track of the most frequent one.

问候！

这篇关于prolog:列表中最大重复的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！