Prolog:查找列表中的第二大元素

Question

我知道如何找到列表中最大的元素 - 没问题,但我该如何寻找第二大元素呢？

假设谓词是secondlargest(+List,?Val)成功的,如果Val是第二大元素List.

如果有最大的并列,那么第二大与最大的相同......

Answer 1

这是O(n)的一种方式.首先,起始谓词,(slne/2).鉴于我们是第二大元素,我们假设您有一个长度至少为2的输入列表(数字).通过比较前两个元素的相对值并记录当前最大值和当前"第二大"(如前面提到的Priyank所建议的)作为调用另一个谓词来完成工作(slne/4)的参数来解决问题:

slne([E0, E1|Es], Res) :-
    E0 > E1, !,
    slne(Es, E0, E1, Res).
slne([E0, E1|Es], Res) :-
    slne(Es, E1, E0, Res).

其次,现在我们已经有了一个引用的起始点,通过列表的其余部分(如果有的话)递归并返回第二个最大的元素(SecMax),在(slne/4)中.

基本案例:不再剩下任何元素!我们完成了.

slne([], _, Res, Res).

下一种情况:我们在列表的开头找到一个新的本地最大值:

slne([E|Es], Max, _SecMax, Res) :-
    E >= Max, !,
    slne(Es, E, Max, Res).

(请注意,我们丢弃了当前的第二大(SecMax),因为我们假设它小于或等于Max).

下一个案例:我们没有找到新的本地最大值,但我们确实找到了新的"第二好":

slne([E|Es], Max, SecMax, Res) :-
    E >= SecMax, !,
    slne(Es, Max, E, Res).

最后一种情况:抛弃其他价值观,因为它们无关紧要 - 请看看其余的价值:

slne([_|Es], Max, SecMax, Res) :-
    slne(Es, Max, SecMax, Res).

而已.就个人而言,我喜欢Juanjo的解决方案,主要是因为它是1行代码,并且即使对于大输入,O(n log n)和O(n)之间的性能差异在实践中也可以忽略不计.(另请注意,dsort/2并未出现在所有PROLOG实现中 - 例如,在SWI-PL中,您可能会尝试msort/2使用).

Answer 2

以下是使用size-3 排序网络与clpfd结合使用的方法:

:- use_module(library(clpfd)).

zs_secondlargest([Z1,Z2|Zs], X) :-
   T1 #= max(Z1,Z2),
   T2 #= min(Z1,Z2),
   zs_secondlargest_(Zs, X, T1, T2).

zs_secondlargest_([], X, _, X).
zs_secondlargest_([Z|Zs], X, A1, A2) :-
   B2 #=     max(A2,Z),
   C1 #= max(min(A2,Z),A1),
   D1 #= max(C1,B2),
   D2 #= min(C1,B2),
   zs_secondlargest_(Zs, X, D1, D2).

使用SICStus Prolog 4.3.2进行示例查询:

| ?- zs_secondlargest([2,4,8,3,5,8,7], X).
X = 8 ? ;            %     8  >= 8
no
| ?- zs_secondlargest([6,4,3,6,3,4,8,6], X).
X = 6 ? ;            %             8>6
no
| ?- zs_secondlargest([2,3,5,4,1,6,7,3,9], X).
X = 7 ? ;            %             7 < 9
no
| ?- zs_secondlargest([2,3,5,4,1,6,7,3,9,8], X).
X = 8 ?              %                 9>8
yes

Answer 3

不知道序言，但一般来说我们不能存储两个变量，一个用于最高的变量，一个用于第二高的变量。

if(a >= x)
  b = a
  a = x