Какой элемент списка является наиболее распространенным

Question

Я пытаюсь найти самый распространенный элемент списка ([b, a, a, a, c, d, b, f, s, f, s, f, s, f, s, f, f ], R) поэтому результат должен быть R = f, Я думал, что если мы возьмем список, перейдем в конец списка, возьмем el = b, num1 = 1, затем вернемся к началу и сравним, если b = b, num1 = num1 + 1, иначе a! = B, тогда если num2 = num2 + 1, num1> num2 рекурсия, в противном случае el = a или что-то в этом роде, но у меня возникли некоторые трудности с преобразованием его в Пролог.

insert_sort сортирует список, но по какой-то интересной причине, если я использую las(X,Y) (я переопределяю исходное last/2), я получаю 4-a, если я использую last(X,Y), я получаю просто ...

most_common([X|Y],J):-
    insert_sort([X|Y],[R|Rs]),             
    count_runs([R|Rs],G),
    las(G,J).

las([N-Y],Y).
las([_|T],Y):- las(T,Y).
las([_|Tail], Y) :- las(Tail, Y).

insert_sort(List,Sorted):-
   i_sort(List,[],Sorted).

i_sort([],Acc,Acc).
i_sort([H|T],Acc,Sorted):- 
    insert(H,Acc,NAcc),
    i_sort(T,NAcc,Sorted).

insert(X,[],[X]).     
insert(X,[Y|T],[Y|NT]):- X @> Y, insert(X,T,NT).
insert(X,[Y|T],[X,Y|T]):- X @=< Y.

Answer 1

Сохранение логическая чистота используя list_counts/2 для определения mostcommonitem_in/2 следующим образом:

mostcommonitem_in(E,Xs) :-
   list_counts(Xs,Cs),                      % tag items with multiplicity
   maplist(\ (X-N)^(M-X)^(M is -N),Cs,Ps),  % prepare keysorting
   keysort(Ps,[Max-_|_]),                   % sort ascending by negated count
   member(Max-E,Ps).                        % pick most common ones

Давайте запустим запрос!

?- mostcommonitem_in(X,[a,b,c,d,a,b,c,a,b]).
X = a ;
X = b ;
false.                                % OK

Но это все еще монотонно?

?- mostcommonitem_in(X,[A,B,C,D,A,B,C,A,B]), A=a,B=b,C=c,D=d.
X = A, A = a, B = b, C = c, D = d ;
X = B, B = b, A = a, C = c, D = d ;
false.                                % OK: monotone

Есть скорость? (по сравнению с чистым ответом, который я показал в моем предыдущем ответе на этот вопрос )

% OLD
?- length(Xs,<b>5</b>), time(findall(t,mostcommon_in(E,Xs),Ts)), length(Ts,N_sols).
% 854,636 inferences,    0.115 CPU in <b>0.115 seconds</b> (100% CPU, 7447635 Lips)
N_sols = 71,   Xs = [_,_,_,_,_],     Ts = [t,t,t|...].    
?- length(Xs,<b>6</b>), time(findall(t,mostcommon_in(E,Xs),Ts)), length(Ts,N_sols).
% 4,407,975 inferences,  0.449 CPU in <b>0.449 seconds</b> (100% CPU, 9813808 Lips)
N_sols = 293,  Xs = [_,_,_,_,_,_],   Ts = [t,t,t|...].
?- length(Xs,<b>7</b>), time(findall(t,mostcommon_in(E,Xs),Ts)), length(Ts,N_sols).
% 24,240,240 inferences, 2.385 CPU in <b>2.384 seconds</b> (100% CPU, 10162591 Lips)
N_sols = 1268, Xs = [_,_,_,_,_,_,_], Ts = [t,t,t|...].

% NEW
?- length(Xs,<b>5</b>), time(findall(t,mostcommonitem_in(E,Xs),Ts)), length(Ts,N_sols).
% 4,031 inferences, 0.001 CPU in  <b>0.002 seconds</b> (93% CPU, 2785423 Lips)
N_sols = 71,   Xs = [_,_,_,_,_],     Ts = [t,t,t|...].    
?- length(Xs,<b>6</b>), time(findall(t,mostcommonitem_in(E,Xs),Ts)), length(Ts,N_sols).
% 17,632 inferences, 0.002 CPU in <b>0.002 seconds</b> (100% CPU, 9194323 Lips)
N_sols = 293,  Xs = [_,_,_,_,_,_],   Ts = [t,t,t|...].    
?- length(Xs,<b>7</b>), time(findall(t,mostcommonitem_in(E,Xs),Ts)), length(Ts,N_sols).
% 82,263 inferences, 0.023 CPU in <b>0.023 seconds</b> (100% CPU, 3540609 Lips)
N_sols = 1268, Xs = [_,_,_,_,_,_,_], Ts = [t,t,t|...].

Answer 2

Это похоже на домашнюю работу, поэтому я не собираюсь давать вам полный ответ, но предложу, как вы могли бы решить ее одним конкретным способом, что не обязательно является лучшим способом:

• Сортировка списка в отсортированном порядке (по стандартному порядку условий, если это достаточно хорошо): посмотрите на sort/2 подпрограммы.например, [b,a,a,a,c,d,b] становится [a,a,a,b,b,c,d].

• Возьмите отсортированный список и посчитайте размер «прогонов», возможно, для преобразования [a,a,a,b,b,c,d] в [3-a,2-b,1-c,1-d] (где - / 2 - просто другой термин).например, рассмотрим следующий код:

---

count_runs([E|Es], C) :-
      % defer to count_runs/3 with an initial count of element E
    count_runs(Es, 1-E, C).

  % return the final count for Y elements if none remain (base case)
count_runs([], N-Y, [N-Y]). 

count_runs([X|Es], N-Y, [N-Y|Rest]) :-
      % if X is not equal to Y, record the count and continue next run
    X \== Y, !,  
    count_runs([X|Es], Rest).

count_runs([_X|Es], N-Y, Rest) :-
      % else X equals Y; increment the counter and continue
    NPlusOne is N + 1,
    count_runs(Es, NPlusOne-Y, Rest).

---

• Выполните что-то вроде keysort/2, чтобы упорядочить термины по значениюих ключей (то есть числа, которые являются счетами, превращая [3-a,2-b,1-c,1-d] в [1-c,1-d,2-b,3-a]).Затем наиболее часто встречающимися элементами списка являются значения в конце списка с одинаковым значением ключа (т. Е. Здесь это a в последнем члене 3-a).В общем, это может быть больше, чем один элемент, который встречается больше всего (в равной степени с другим).

Удачи.

Answer 3

На основе Пролог лямбда мы используем мета-предикаты tcount/3 и reduce/3, а также предикат равенства равенства в терминах (=)/3:

:- use_module(library(lambda)).

mostcommon_in(E,Xs) :-
   tcount(=(E),Xs,M),
   maplist(Xs+\X^N^(tcount(=(X),Xs,N)),Xs,Counts),
   reduce(\C0^C1^C^(C is max(C0,C1)),Counts,M).

Пример запроса:

?- mostcommon_in(X,[<b>a</b>,<i>b</i>,c,d,<b>a</b>,<i>b</i>,c,<b>a</b>,<i>b</i>]).
X = a ;
X = b ;
false.

Обратите внимание, что это monotone (в отличие от более ранней версии быстрого взлома).Смотри!

?- mostcommon_in(X,[A,B,C,D,A,B,C,A,B]), A=a,B=b,C=c,D=d.
<b>X = a</b>, A = a, B = b, C = c, D = d ;
<b>X = b</b>, A = a, B = b, C = c, D = d ;
false.

Answer 4

Я мог бы дать вам высокоуровневый ответ: вы можете отсортировать список, а затем сравнительно легко подсчитывать элементы один за другим и обновлять то, что на данный момент является наиболее распространенным элементом.