CODEWITHSUNDEEP
prolog
Darlyn
Darlyn

Reputation: 4938

Finding second min value in list

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?

Upvotes: 3

Views: 913

Answers (3)

Felix Dombek
Felix Dombek

Reputation: 14356

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

Upvotes: 2

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476554

First of all, your implementation of findmin/2 is not very efficient:

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

Since it does not use tail recursion. You better transform this into a clause with tail recursion and an accumulator.

You can - as is suggested by @DanielLyons sort the list and then retrieve the second element, but this requires O(n log n) time complexity for the sorting step. The sorting is however done in low level C on most Prolog systems; but eventually, if the list is very large, a linear apporach will outperform it.

You can also use @FelixDombek's approach by storing the two values into a list. One can slightly improve the efficiency of this approach by:

  • not using a list, but simply two parameters since it will save on pattern matching and tuple construction; and
  • use an if-then-else approach to save on comparisons.

This results in transforming the program into:

find2nd([H1,H2|T],Min2) :-
    H1 =< H2 ->
    find2nd(T,H1,H2,Min2)
   ;find2nd(T,H2,H1,Min2).

find2nd([],_,Min2,Min2).
find2nd([H|T],H1,H2,Min2) :-
    H >= H2 ->
    find2nd(T,H1,H2,Min2)
   ;(  H >= H1 ->
       find2nd(T,H1,H,Min2)
      ;find2nd(T,H,H1,Min2)
    ).

Upvotes: 1

Daniel Lyons
Daniel Lyons

Reputation: 22803

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.

Upvotes: 4

Related Questions