prolog - A program that finds the Kth largest element in a list

Question

Am writing a logic program for kth_largest(Xs,K) that implements the linear algorithm for finding the kth largest element K of a list Xs. The algorithm has the following steps:

1. Break the list into groups of five elements.
2. Efficiently find the median of each of the groups, which can be done with a fixed number of comparisons.
3. Recursively find the median of the medians.
4. Partition the original list with respect to the median of the medians.
5. Recursively find the kth largest element in the appropriate smaller list.

How do I go about it? I can select an element from a list but I don't know how to get the largest using the above procedure.Here is my definition for selecting an element from a list

select(X; HasXs; OneLessXs)  
% The list OneLessXs is the result of removing
% one occurrence of X from the list HasXs.
select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]) :-  select(X,Ys,Zs).

Answer 1

I'm going to jump in since no one has attempted an Answer, and hopefully shed some light on the procedure to be programmed.

I've found the Wikipedia article on Selection algorithm to be quite helpful in understanding the bigger picture of "fast" (worst-case linear time) algorithms of this type.

But what you asked at the end of your Question is a somewhat simpler matter. You wrote "How do i go about it? I can select an element from a list but i dont know how to get the largest using the above procedure." (emphasis added by me)

Now there seems to be a bit of confusion about whether you want to implement "the above procedure", which is a general recipe for finding a kth largest element by successive searches for medians, or whether you ask how to use that recipe to find simply the largest element (a special case). Note that the recipe doesn't specifically use a step of finding the largest element on its way to locating the median or the kth largest element.

But you give the code to find an element of a list and the rest of that list after removing that element, a predicate that is nondeterministic and allows backtracking through all members of the list.

The task of finding the largest element is deterministic (at least if all the elements are distinct), and it is an easier task than the general selection of the kth largest element (a task associated with order statistics among other things).

Let's give some simple, hopefully obviously correct, code to find the largest element, and then talk about a more optimized way of doing it.

maxOfList(H,[H|T]) :-  upperBound(H,T), !.
maxOfList(X,[_|T]) :-  maxOfList(X,T).

upperBound(X,[ ]).
upperBound(X,[H|T]) :-
    X >= H,
    upperBound(X,T).

The idea should be understandable. We look at the head of the list and ask if that entry is an upper bound for the rest of the list. If so, that must be the maximum value and we're done (the cut makes it deterministic). If not, then the maximum value must occur later in the list, so we discard the head and continue recursively searching for an entry that is an upper bound of all the subsequent elements. The cut is essential here, because we must stop at the first such entry in order to know it is a maximum of the original list.

We've used an auxiliary predicate upperBound/2, which is not unusual, but the overall complexity of this implementation is worst-case quadratic in the length of the list. So there is room for improvement!

Let me pause here to be sure I'm not going totally off-track in trying to address your question. After all you may have meant to ask how to use "the above procedure" to find the kth largest element, and so what I'm describing may be overly specialized. However it may help to understand the cleverness of the general selection algorithms to understand the subtle optimization of the simple case, finding a largest element.

Added:

Intuitively we can reduce the number of comparisons needed in the worst case by going through the list and keeping track of the largest value found "so far". In a procedural language we can easily accomplish this by reassigning the value of a variable, but Prolog doesn't allow us to do that directly.

Instead a Prolog way of doing this is to introduce an extra argument and define the predicate maxOfList/2 by a call to an auxiliary predicate with three arguments:

maxOfList(X,[H|T]) :- maxOfListAux(X,H,T).

The extra argument in maxOfListAux/3 can then be used to track the largest value "so far" as follows:

maxOfListAux(X,X,[ ]).
maxOfListAux(Z,X,[H|T]) :-
    ( X >= H  -> Y = X ; Y = H ),
    maxOfListAux(Z,Y,T).

Here the first argument of maxOfListAux represents the final answer as to the largest element of the list, but we don't know that answer until we have emptied the list. So the first clause here "finalizes" the answer when that happens, unifying the first argument with the second argument (the largest value "so far") just when the tail of the list has reached the end.

The second clause for maxOfListAux leaves the first argument unbound and "updates" the second argument accordingly as the next element of the list exceeds the previous largest value or not.

It isn't strictly necessary to use an auxiliary predicate in this case, because we might have kept track of the largest value found by using the head of the list instead of an extra argument:

maxOfList(X,[X]) :- !.
maxOfList(X,[H1,H2|T]) :-
    ( H1 >= H2  -> Y = H1 ; Y = H2 ),
    maxOfList(X,[Y|T]).