Finding second min value in list

Question

I have defined the predicate that finds the minimum value in list e.g

greater(X,Y):- X > Y.
isLower(X,Y):- X < Y.


findmin( [X]   , X ).
findmin( [H|T] , P ):- findmin(T,P1) , isLower(H,P1), P is H.
findmin( [H|T] , P) :- findmin(T,P1) , greater(H , P1), P is P1.

However i have hard time modifying this code to find second minimum value including nested lists.

How could i assure that the second minimum value will be returned?

Answer 1

I mean this mostly as a joke, but here it is:

find_second_min(L, Min2) :- sort(L, [_, Min2|_]).

So, sorting will definitely put all your items in order. You could get the minimum by just looking at the top one. If you want want the two smallest, you can look at the first two elements:

find_mins(L, Min1, Min2) :- sort(L, [Min1, Min2|_]).

As you know, sorting is O(N log N) while you can find just the minimum in O(N). So to find just one value this is probably too much work. But it's cute.

Answer 2

You could simply make P a list containing the two smallest numbers. Then you would need to check for each element if it is smaller than the larger one in P, and if so, replace it. Then in the end, the larger of the two is the second largest element.

By the way, you really don't need to define your own greater/isLower – why not just use the operators that are built in, >/< in their place?

This would also make it a bit easier to spot the bug you have in your code if H is exactly as large as P1.

So, here's how I would do it:

find2nd([H1, H2 | T], M) :- H1 < H2, !, find2nd_i(T, M, [H1, H2]).
find2nd([H1, H2 | T], M) :- H1 >= H2, find2nd_i(T, M, [H2, H1]).

find2nd_i([], M2, [_, M2]).
find2nd_i([H | T], M, [M1, M2]) :- H >= M2, !, find2nd_i(T, M, [M1, M2]).
find2nd_i([H | T], M, [M1, M2]) :- H < M2, H >= M1, !, find2nd_i(T, M, [M1, H]).
find2nd_i([H | T], M, [M1, M2]) :- H < M2, H < M1, find2nd_i(T, M, [H, M1]).