Пролог: функция, которая возвращает наиболее частый элемент в списке

Question

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

найти наиболее рекурсивный элемент и время его нахождения внутри списка

Есть идеи?Я новичок в Прологе и прошу ради моего задания, поэтому, если кто-то собирается помочь мне просто дать мне подсказку или просветить меня, я не хочу, чтобы какой-либо реальный код копировал вставку.

Answer 1

foldl может быть вашим другом:

:- use_module(library(lambda)).
count_repeat(L, R, N) :-
    foldl(\X^Y^Z^(select(V-X, Y, Y1)-> V1 is V+1, Z = [V1-X|Y1]; Z = [1-X|Y]), L, [], L1),
    sort(L1,L2),
    last(L2, N-R).

Результат:

? - count_repeat ([3,2,6,2,4,1,4,2,5,3,2,4,1,2,3,1,2,4,5,3,2], R, N).

R = 2,

N =7.

Answer 2

библиотека ( агрегат ) заслуживает изучения ...

?- L=[1,2,3,3,3,1,2,3],aggregate(max(C,E),aggregate(count,member(E,L),C),R).
L = [1, 2, 3, 3, 3, 1, 2, 3],
R = max(4, 3).

edit : учет требования о вхождениях относительно длины списка:

?- L=[3,2,6,2,4],length(L,Len),HalfLen is Len/2, aggregate(max(C,E),(aggregate(count,member(E,L),C),C>HalfLen),R).
false.

Answer 3

Существует способ (ну, бесконечные способы) решить эту проблему с помощью встроенных прологов, таких как sort/2, findall/3, member/2, include/3 и length/2:

?- List=[3,2,6,2,2,1,4,2,2,2,2,4,1,2,3,2,2,4,2,3,2],
    sort(List, Uniq),                 % sort removing duplicate elements
    findall([Freq, X], (
        member(X, Uniq),              % for each unique element X
        include(=(X), List, XX),      %
        length(XX, Freq)              % count how many times appears in List
    ), Freqs),
    sort(Freqs, SFreqs),              % sort (by frequency)
    last(SFreqs, [Freq, MostCommon]), % last pair is the most common
    length(List, ListLen),
    Freq > ListLen/2.                 % is frequency greater than half list length?

Список = [3, 2, 6, 2, 2, 1, 4, 2, 2 | ...],

Uniq = [1, 2, 3, 4, 6],

Freqs = [[2, 1], [12, 2], [3, 3], [3, 4], [1, 6]],

SFreqs = [[1, 6], [2, 1], [3, 3], [3,4], [12, 2]],

Freq = 12,

MostCommon = 2,

ListLen = 21.

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

Другой способ, более эффективный, будет использовать msort/2 и затем создайте кодировку по длине прогона отсортированного списка, затем снова отсортируйте его и выберите элемент, представляющий наиболее часто встречающийся элемент.Сейчас я не могу понять, как выполнить кодирование по длине прогона без определения вспомогательных рекурсивных предикатов, поэтому вот оно:

count_repeated([Elem|Xs], Elem, Count, Ys) :-
    count_repeated(Xs, Elem, Count1, Ys), Count is Count1+1.
count_repeated([AnotherElem|Ys], Elem, 0, [AnotherElem|Ys]) :-
    Elem \= AnotherElem.
count_repeated([], _, 0, []).

rle([X|Xs], [[C,X]|Ys]) :-
    count_repeated([X|Xs], X, C, Zs),
    rle(Zs, Ys).
rle([], []).

, тогда получение наиболее распространенного элемента можно сделать с помощью:

?- List=[3,2,6,2,2,1,4,2,2,2,2,4,1,2,3,2,2,4,2,3,2],
    msort(List, SList),
    rle(SList, RLE),
    sort(RLE, SRLE),
    last(SRLE, [Freq, MostCommon]),
    length(List, ListLen),
    Freq > ListLen/2.

Список = [3, 2, 6, 2, 2, 1, 4, 2, 2 | ...],

SList = [1, 1, 2,2, 2, 2, 2, 2, 2 | ...],

RLE = [[2, 1], [12, 2], [3, 3], [3, 4],[1, 6]],

SRLE = [[1, 6], [2, 1], [3, 3], [3, 4], [12, 2]],

Freq = 12,

MostCommon = 2,

ListLen = 21.