哪個列表項是最常見的

Question

我試圖找到最常見的列表項common（[b，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遞歸else el = a或類似的東西，但我有一些困難轉換成Prolog。

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

這看起來像功課，所以我不會給你一個完整的答案，但會建議你怎麼可能在一個特定的方式，這並不一定是最好的方式解決這個問題：

• 將列表按排序順序排序（如果足夠好，按標準順序排列）：查看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 2

我可以給你一個高層次的答案：你可以對列表進行排序，然後相對容易地計數項目，一個接一個，並更新迄今爲止最常見的項目。

Answer 3

基於Prolog lambdas，我們使用元謂詞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,[a,b,c,d,a,b,c,a,b]). 
X = a ; 
X = b ; 
false. 

注意，這是單調（與之前的快速版本不同）。看！

 
?- mostcommon_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, A = a, B = b, C = c, D = d ; 
false. 

Answer 4

使用list_counts/2 定義mostcommonitem_in/2如下保留logical-purity：

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 

速度有多快？ （相對於純答案我在my previous answer to this question顯示）

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

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