find the second largest element in the list

Question

I know how to find the largest element of the list no problem, but how should I go about finding the second larget 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...

I'm quite new to Prolog, can someone help me? Thanks!!

Answer 1

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

Answer 2

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.

Answer 3

Hi

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.

Regards

Mark

Answer 4

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 :)

Answer 5

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

Answer 6

Meh, you've had a day to work it out, so here we go!

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

Answer 7

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