如何在Prolog中找到列表的众数？

Question

请问有人能告诉我如何在Prolog中找到列表的众数吗？

我尝试了以下方法：

count_elt([], _, 0) :- !. 
count_elt([H|T], H, P) :- 
  count_elt(T, H, P1),
  P is P1 + 1, !. 
count_elt([_|T], E, P) :- count_elt(T, E, P). 

listMode([], 0) :- !. 
listMode([_], 1) :- !. 
listMode([H1|[H2|T]], M) :- 
  count_elt([H1|[H2|T]], H1, C),
  listMode([H2|T], C1),
  C > C1,
  M is C, !. 
listMode([_|[H2|T]], M) :- listMode([H2|T], M).

现有的函数只返回列表中出现次数最多的值，但我需要返回出现次数最多的元素（列表中最频繁出现的值）。

- Dinithi De Silva

Answer 1

您离解决问题其实已经很接近了，但是需要更多的非确定性。简单来说，您需要找到一种使用更少切割的方式表达count_elt/3，因为目前的做法可能会导致以下情况：

?- count_elt([a,b,a,a,c,b,d,e,a,f], Y, X).
Y = a,
X = 4.

你想要得到的是这样的：

?- count_elt([a,b,a,a,c,b,d,e,a,f], Y, X).
Y = a,
X = 4 ;
Y = b,
X = 2 ;
Y = c,
X = 1 ;
...
Y = f,
X = 1 ;
false.

从那里开始，你只需要找到具有最大值的解决方案，可以使用setof/3或逻辑表达式或使用aggregate库来实现。因此，首先修复count_elt/3，然后从那里开始。编辑：一些一般性评论：1.您可以将[H1|[H2|T]]写为[H1,H2|T]，这样更清晰。2.listMode/2应该返回第二个位置的项目而不是计数。由于您需要计数来执行此过程，因此您可能需要创建一个listMode/3或listMode/5助手来在递归期间管理状态。 编辑：解决方案。由于@MaDu_LK已经决定展示解决方案，尽管这很可能是家庭作业，我想分享我的解决方案，使用@false的重ified equality predicate：

count_of([],         _,  0).
count_of([H|Rest], E, N1) :- 
  equality_reified(H, E, Bool),
  count_of(Rest, E, N0),
  (Bool == true -> N1 is N0 + 1 ; N1 = N0).

frequency(L, I, N) :-
  sort(L, LSorted),
  member(I, LSorted),
  count_of(L, I, N).

mode(L, X) :-
  frequency(L, X, NMax),
  \+ (frequency(L, _, NBigger),
      NMax < NBigger).

这种方法的性能要更好一些：

% MaDu_LK
?- time(get_mode([a,b,c,a,b,c,a,a,b,c,a,d,b], X)).
% 2,811 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 7117429 Lips)
X = a.

% mine
?- time(mode([a,b,c,a,b,c,a,a,b,c,a,d,b], X)).
% 217 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 3144928 Lips)
X = a ;
% 195 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 3305085 Lips)
false.

另一种解决方案也只产生一个模式，即使列表是多峰的：

% MaDu_LK
?- get_mode([a,a,b,b,c], X).
X = a.

% mine
?- mode([a,a,b,b,c], X).
X = a ;
X = b ;
false.

思考的食品。

- Daniel Lyons

---

count_of/3 可以使用一些具体化等式来使其正确且高效（参考https://dev59.com/LWYr5IYBdhLWcg3wdp4B）。目前它既不正确也不高效。 - false

@false 看一下修改，让我知道你是否明白。 - Daniel Lyons

不！你仍在创建不必要的选择点。equality_reified 的想法是允许索引，通过使用它一次，然后在结果上进行索引。以这种方式，只要术语是=或dif，就没有选择点。只有当它们之间时才需要支付。 - false

好的！但是仍然缺少的（但这只是为了完美），就是尾递归。 - false

谢谢！我需要使用累加器参数重写才能获得尾递归性，对吗？ - Daniel Lyons

是的。但理想情况下，算术应该放在递归之前，这样可以使用 clpfd 改善终止；并且编译会将其转换为完美代码... - false

Answer 2

你已经从Daniel那里得到了关于你的代码的好建议。我将展示一种使用库(aggregate)来获取信息的替代方法：

mode_of_list(L, M) :-
    setof(C-E, (member(E, L), aggregate(count, member(E, L), C)), M).

测试

?- mode_of_list([a,b,a,a,c,b,d,e,a,f],L).
L = [1-c, 1-d, 1-e, 1-f, 2-b, 4-a].

- CapelliC

---

反例：mode_of_list([],M) 应该成功，但是你的定义失败了。mode_of_list([a,X],M) 有两个独立的答案。 - false

空列表为什么需要模式？ - Daniel Lyons

在变量存在的情况下，行为相当复杂。另一方面，我认为使用带有变量的列表属于高级用法... - CapelliC

Answer 3

希望您已经得到了一些建议。以下是适用于您的工作代码。

count_elt([],_,0):-!.
count_elt([H|T],H,C):-count_elt(T,H,C1),C is C1+1,!.
count_elt([_|T],E,C):-count_elt(T,E,C).

listMode([],0) :- !.
listMode([_],1) :- !.
listMode([H1|[H2|T]], M) :-count_elt([H1|[H2|T]],H1,C),listMode([H2|T],C1),C > C1,M is C,!.
listMode([_|[H2|T]],M) :- listMode([H2|T],M).

get_mode([H|T],M):-listMode([H|T],K),count_elt([H|T],M,K).

- Madusanka