Prolog: Finding the second largest element in a list

I know how to find the largest element of a list—no problem, but 开发者_JS百科how should I go about finding the second largest element?

Say the predicate is secondlargest(+List,?Val) and succeeds if Val is the second largest element in the List.

If there is a tie for largest, then second largest is the same as largest...

Here's one way of doing it O(n). First off, the starting predicate, (slne/2). Given we're after the 2nd largest element, we'll assume you have an input list (of numbers) with length of at least two. Kick things off by comparing the relative values of the first two elements and record the current maximum and the current '2nd largest' (as suggested earlier, by Priyank), as arguments to a call to another predicate to do the work (slne/4):

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

Secondly, now that we've got a starting point of reference, recurse through the remainder of the list (if any) and return the second largest element (SecMax), in (slne/4).

The base case: No more elements left! We're finished.

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

The next case: we find a new local maximum at the start of the list:

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

(Note that we threw away the current second largest (SecMax), because we assume that it was smaller than or equal to Max).

The next case: we don't find a new local maximum, but we do find a new '2nd best':

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

The last case: Throw away other values, as they're irrelevant - look at the rest instead:

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

That's it. Personally, I like Juanjo's solution, mainly because it's 1 line of code, and the performance difference between O(n log n) and O(n) might be negligible in practice even for large input. (Also note that dsort/2 doesn't appear in all PROLOG implementations - e.g., in SWI-PL, you might try msort/2 instead).

Here's how you could do it using size-3 sorting networks in combination with 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).

Sample queries using 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

Here is my proposal for a clpfd variant of @sharky's version using if_/3. Firstly, here is a reifying version of the greater-equal to relation using clpfd:

geq_to_t(X,Y,T) :-
   (X#>=Y) #<==> B,
   bool10_t(B,T).

bool10_t(1,true).
bool10_t(0,false).

With geq_to_t/3 and if_/3 the predicate can be defined like so:

% this corresponds to @sharky's slne/2:
sl_of(SL,[X1,X2|Xs]) :-
   if_(geq_to_t(X1,X2),
       max_sl_of_(X1,X2,Xs,SL),
       max_sl_of_(X2,X1,Xs,SL)).

% this corresponds to @sharky's slne/4:
max_sl_of_(_M,SL,[],SL).                 % base case
max_sl_of_(M,SL,[X|Xs],R) :-
   if_(geq_to_t(X,M),                    % if X#>=M
       max_sl_of_(X,M,Xs,R),             % X is new maximum
       if_(geq_to_t(X,SL),               % else if X#>=SL
           max_sl_of_(M,X,Xs,R),         % X is new 2nd largest
           max_sl_of_(M,SL,Xs,R))).      % else X is not of interest

Note that I flipped the order of the arguments in order to use a more desciptive naming (sl_of/2), so the list is now the second argument. As demanded in the bounty description, there are no useless choicepoints left if the second argument is ground:

   ?- sl_of(SL,[1,2,3,4,5,6]).
SL = 5
   ?- 

Samples from answer by @repeat:

   ?- sl_of(SL,[2,4,8,3,5,8,7]).
SL = 8
   ?- sl_of(SL,[6,4,3,6,3,4,8,6]).
SL = 6
   ?- sl_of(SL,[2,3,5,4,1,6,7,3,9]).
SL = 7
   ?- sl_of(SL,[2,3,5,4,1,6,7,3,9,8]).
SL = 8

Don't know about prolog but in general can't we store two variable, one for the highest and one for the second highest.

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

I will tell you two different algorithms. First one is easy, the second one is a bit tricky.

1. Write a Merge Sort function(Descending order), then just pick the second element. This is easy but it takes O(nlogn) time.

2. In general for any k you can solve this by the following algorithm. This runs in linear time.

--Break the list into group of five elements
--Find the median of each group, which can be done with a fixed number of comparisons
--Recursively find medians or medians
--Partition the original List wrt medians of medians
--Recursively find the kth largest element in the appropriate smaller list.

You can find a more detailed discussion on this algorithm in "Introduction To Algorithms by Cormen" Chapter -9

I would recommend you too try implementing it on your own without seeing any existing implementation. I had a lot of fun implementing this algorithm in prolog :)

This is an idiom to be used in any language:

Loop over the list, count each element and insert into another list data to tell you the element, and it's size. Sort the list in descending order. Move the list pointer to the 2nd element. You have the 2nd largest element now.

This is how you do it in Prolog:

secondLargest(L, Y) :- dsort(L, [X,Y|T])

Where dsort works like this:

?- dsort([2,3,4,2,1], L).
L = [4,3,2,2,1]

You can implement dsort by your own, the hacky part is how I wrote the list [X,Y|T]. That's read: the list is made of 2 elements (X and Y) and a tail (T).

another (not the best obviously) approach would be as follows: 1. find max element in list L 2. remove max element from list L and get new list L1 3. find max in L1 and return it

First task: implement a sort predicate, if that's beyond your capabilities right now, look in Clocksin and Mellish.

Second task: write a predicate which selects the head of the tail of a list. Apply this predicate to your sorted list.

OR, since you already know how to select the largest element in a list, write a predicate to drop the largest element of a list, and apply your existing predicate to the remainder of the original list.

Sometimes dsort doesn't work in some versions of SWI-Prolog like mine. So, This is the simplest code:

secondLargest(List,X):-
        msort(List,SortedList),reverse(SortedList,[_|[X|_]]).