Максимальное количество вхождений в списке - PullRequest
Новая
       23

Максимальное количество вхождений в списке

0 голосов
/ 20 мая 2011

Я пытаюсь написать функцию Prolog, которая с учетом списка возвращает элемент (ы), который повторяется в этом списке чаще всего, например:

['a', 'a', 'b', 'c', 'b'] должны возвращать ['a', 'b'] ['c', 'a', 'a', 'c', 'b', 'c', 'b'] должны возвращать ['c'] и т.д ...

Я пытаюсь сделать это с помощью другой функции (которая подсчитывает, сколько раз что-то существует в списке (countlist), но я никуда не попадаю. Небольшая помощь, пожалуйста? 

listMax(In, Out) :-
    listMax(In, Out, 0).

listMax([H | L], [H | O], Max) :-
    countlist(H, [H | L], N),   
    N > Max,
    listMax(L, [H | O], N).

listMax([H | L], O, Max) :-
    countlist(H, [H | L], N),
    <=(Max, N),
    listMax(L, O, Max).

listMax([], [], _Max).

listMax([], _O, _Max).

Ответы [ 2 ]

1 голос
/ 20 мая 2011

Как насчет этого: 

listmax(L, M):-
 listmax(L, [], [], M).

listmax([], Seen, MMax, Max):-
  MMax=[] -> Max=Seen ; listmax(MMax, [], [], Max).
listmax([H|T], Seen, MMax, Max):-
  (member(H, Seen) ->
    listmax(T, Seen, [H|MMax], Max) ;
    listmax(T, [H|Seen], MMax, Max)).

Вот небольшое объяснение этого алгоритма:

Идея состоит в том, чтобы перебрать список, удаляя первое вхождение каждого элемента, которое приводит к новомусписок.Затем рекурсивно применяйте тот же алгоритм к этому новому списку, пока в результате мы не получим пустой список.На данный момент мы знаем, что предыдущий список - это список, который мы ищем.

Второе предложение listmax / 4 - это итеративное предложение, которое проверяет, отображается ли элемент в первый раз.Список видимых предметов хранится во втором аргументе этого предиката.Третий аргумент собирает оставшиеся элементы (те, которые не видны в первый раз).

Первый пункт listmax / 4 является базовым случаем.Это вступает в игру, когда мы закончим итерацию по списку.На этом этапе он проверяет, является ли список оставшихся элементов пустым, и в этом случае мы знаем, что список увиденных - это список, который мы ищем.В противном случае мы снова применяем алгоритм, но в качестве входного списка используем «оставшийся список».

0 голосов
/ 21 мая 2011 

listmax(In,Out) :-
        setof(A,member(A,In),L1),
        findall([Count,A],(
                    member(A,L1),
                    count(A,In,Count)),
               L2),
        max_1(L2,Max),
        findall(A,member([Max,A],L2),Out).

count(A,[],0).
count(A,[A|R],X) :-
        count(A,R,Y),
        X is Y + 1.
count(A,[_|R],X) :-
        count(A,R,X).

max_1(L,Max) :-
        findall(A,member([A|_],L),L1),
        max(L1,Max).
...