哪个列表项是最常见的

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|...].