Prolog中列表中的重复元素

Question

我想找到一种方法，在一个列表中找到最多重复的元素，如果两个元素重复次数相同。我希望谓词是一个包含这两个元素的列表。我该怎么做？

示例查询和预期答案：

?- maxRepeated([1,3,3,4,2,2],X).
X = [3,2].

% common case: there is one element that is the most repeated
?- maxRepeated([1,3,3,3,3,4,2,2],X).
X = [3].

% all elements repeat the same number of times
?- maxRepeated([1,3,4,2],X).
X = [1,3,4,2].

我遇到了与最少重复元素相同的问题。

- user3657716

---

这是一项作业任务吗？您是否尝试过解决方案？此外，重复元素是否总是连续的？例如，[1,3,2,1,3,3,1,4,1]怎么处理？ - lurker

这是我正在尝试开发的一个项目，它基于我在课堂上学到的一些相关内容。我知道如何获取单个结果，但不知道如何获取列表。而且，元素并不总是连续的。感谢您的回答。 - user3657716

@user3657716，你解决了你的问题吗？ - rpax

Answer 1

谓词mostcommonitems_in/2（将在本答案中介绍）与我之前某个答案中定义的mostcommonitem_in/2有很多相似之处（链接）。

以下我们使用list_counts/2、Prolog lambda、foldl/4、tchoose/3和(=)/3：

:- use_module(library(lambda)).

mostcommonitems_in(Ms,Xs) :-
   list_counts(Xs,Cs),
   foldl(\ (_-N)^M0^M1^(M1 is max(M0,N)),Cs,0,M),
   tchoose(\ (E-N)^E^(N=M), Cs,Ms).

让我们运行一些查询！

首先，OP提供的三个查询：

- mostcommonitems_in(Xs,[1,3,3,4,2,2])。 Xs = [3,2]。 - mostcommonitems_in(Xs,[1,3,3,3,3,4,2,2])。 Xs = [3]。 - mostcommonitems_in(Xs,[1,3,4,2])。 Xs = [1,3,4,2]。

好的！还有一些更具体的查询——感谢@lurker和@rpax。

把列表中恰好出现三次的三个元素找出来，可以这样写：

?- bagof(Item, count(Item,[1,2,3,4,5,6,3,3,3,7,7,8,8]), Items),
   include(=(3), Items, Threes),
   length(Threes, 3).
Threes = [3, 7, 8].

这里用到了`bagof`和`include`两个谓词。`bagof`用于查找所有满足某个条件的元素，并将它们存放在一个列表中；而`include`则是从一个列表中筛选出符合某个条件的元素，返回一个新的列表。

?- mostcommonitems_in(Xs,[a,b,c,a,b,c,a,b,c,x,d,e]).
Xs = [a,b,c].                                          % works as expected 

以下这个稍微更一般化的查询怎么样？

?- mostcommonitems_in(Xs,[A,B,C]).
  Xs = [C]    ,     A=B           ,     B=C
; Xs = [B]    ,     A=B           , dif(B,C)
; Xs = [C]    ,               A=C , dif(B,C)
; Xs = [C]    ,           dif(A,C),     B=C
; Xs = [A,B,C], dif(A,B), dif(A,C), dif(B,C).

上述查询破坏了几乎所有不纯的代码... 我们的Prolog代码是纯粹的，所以我们可以继续进行！

- repeat

Answer 2

我对Prolog不是很了解，可能有更好的方法可以实现，但以下是一个可行的解决方案：（SWI Prolog）

%List of tuples, keeps track of the number of repetitions.
modify([],X,[(X,1)]).
modify([(X,Y)|Xs],X,[(X,K)|Xs]):- K is Y+1.
modify([(Z,Y)|Xs],X,[(Z,Y)|K]):- Z =\= X, modify(Xs,X,K).

highest((X1,Y1),(_,Y2),(X1,Y1)):- Y1 >= Y2.
highest((_,Y1),(X2,Y2),(X2,Y2)):- Y2 > Y1.

maxR([X],X).
maxR([X|Xs],K):- maxR(Xs,Z),highest(X,Z,K).

rep([],R,R).
rep([X|Xs],R,R1):-modify(R,X,R2),rep(Xs,R2,R1).

maxRepeated(X,R):- rep(X,[],K),maxR(K,R).


?- maxRepeated([1,3,3,4,3,2] ,X).
X = (3, 3) .

?- maxRepeated([1,2,3,4,5,6] ,X).
X = (1, 1) .

不重复的元素是类似的。

我认为在这种情况下最好使用元组，但将结果更改为列表也不应该成为问题。

- rpax

---

这个解决方案不满足要求：maxRepeated([1,3,3,4,2,2] ,X). X=[3,2]。 - ApceH Hypocrite

但将结果更改为列表不应该是问题。将（3,2）转换为[3,2]是一个微不足道的操作。 - rpax

你抄袭我的答案，然后给它点踩。你的想象力在哪里？你的创造力在哪里？我在 Stack Overflow 从未遇到过像你这样的人。 - rpax

不，我不是那个downvoter。我的声望太低了。要进行downvote需要125的声望。 - ApceH Hypocrite

Answer 3

这是我在Visual Prolog上的解决方案：

domains
value=integer
tuple=t(value,integer)
list=value*
tuples=tuple*

predicates
modify(tuples,value,tuples)
highest(tuple,tuple,tuple)
maxR(tuples,integer,integer)
maxR(tuples,integer)
rep(list,tuples,tuples)
maxRepeated(list,list)
filter(tuples,integer,list)

clauses
modify([],X,[t(X,1)]):- !.
modify([t(X,Y)|Xs],X,[t(X,K)|Xs]):- K = Y+1, !.
modify([t(Z,Y)|Xs],X,[t(Z,Y)|K]):- Z <> X, modify(Xs,X,K).

highest(t(X1,Y1),t(_,Y2),t(X1,Y1)):- Y1 >= Y2, !.
highest(t(_,Y1),t(X2,Y2),t(X2,Y2)):- Y2 > Y1.

maxR([],R,R):- !.
maxR([t(_,K)|Xs],Rs,R):- K>Rs,!, maxR(Xs,K,R).
maxR([_|Xs],Rs,R):- maxR(Xs,Rs,R).
maxR(X,R):- maxR(X,0,R).

rep([],R,R).
rep([X|Xs],R,R1):-modify(R,X,R2),rep(Xs,R2,R1).

filter([],_,[]):-!.
filter([t(X,K)|Xs],K,[X|FXs]):- !, filter(Xs,K,FXs).
filter([_|Xs],K,FXs):- filter(Xs,K,FXs).

maxRepeated(X,RL):- rep(X,[],Reps),maxR(Reps,K),filter(Reps,K,RL).

goal
maxRepeated([1,3,3,4,2,3,2,2] ,X),
maxRepeated([1,2,3,4,5,6] ,Y).

- ApceH Hypocrite

---

看起来这是我的答案，但更冗长。你不这么认为吗？甚至从句的名称也很常见。 - rpax

我认为是这样，并且不会隐瞒。但是我的版本解决了问题，而你的没有。我拿了你的代码，然后在Visual Prolog上让它工作，并实现了所需的算法。 - ApceH Hypocrite