Member Avatar for bharatk

I am trying to find the index position of the minimum element in a list and print the element at the corresponding index position in another list.

For example:

?- min2(X,Y,[a,b,c],[5,3,7]).
    X= b
    y= 3

Code:

min2(A,B,[A|_],[B|_]).
    min2(A,B,[X|T1],[Y|T2]) :- smallest(W,[Y|T2]),  % using a predicate to find the min element in teh list
                               B is W,              % setting B to the result of above(i.e the min element)
                               min2(A,B,T1,T2).     % looking up position corresponding to min element in list1

the predicate for finding the min element in the list is:

smallest(Head, [Head]).
    smallest(Element, [Head|Tail]) :- smallest(E, Tail), Head =< E, Element is Head.
    smallest(Element, [Head|Tail]) :- smallest(E, Tail), E < Head , Element is E.

The result I am getting is :

X = a,
    Y = 5 ;
    X = b,
    Y = 3 ;
    false.

It somehow picks the first element also. My base case could be wrong? I tried altering the base case to min2(A,B,[A|_],[B|_]). and it breaks.

Please show me where I am going wrong.

Thanks.

  • 2 Contributors
  • 6 Replies
  • 2K Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by bharatk

Dani AI

Generated

Nice question. The extra first solution you saw comes from your base case: min2(A,B,[A|_],[B|_]). literally says "the head pair is a valid answer", so Prolog returns it before doing any work on the tail. Cuts then only hide the symptom. ’s idea of computing the minimum once and then matching positions is the right direction, and you can make it both simple and complete (return all minima) with nth0/3.

Here is a compact, single-query version that:

  • computes the minimum once,
  • finds every index where it occurs,
  • pulls the corresponding element from the first list.
min2(A, Min, Xs, Ys) :-
    Ys \= [],                  % guard: no answer for empty Ys
    min_list(Ys, Min),         % or use your smallest/2 here
    nth0(I, Ys, Min),          % on backtracking, I is every index of Min
    nth0(I, Xs, A).            % pick the aligned element from Xs

Examples:

?- min2(X, Y, [a,b,c], [5,3,7]).
X = b,
Y = 3.

?- min2(X, Y, [a,b,c], [5,3,3]).
X = b,
Y = 3 ;
X = c,
Y = 3.

Notes:

  • This runs in O(n) time for the min_list/2 pass plus O(k) for k occurrences of the minimum, instead of recomputing the minimum at each recursive step (which is O(n^2)).
  • Use =< vs < inside a custom fold if you want first vs last minimum deterministically. The version above is nondet by design, which fixes the "last only" behavior pointed out.
  • Add a length check if you want to fail early on lists of different sizes.

Recommended Answers

All 6 Replies

Member Avatar for TrustyTony

You can not find corresponding element from other list by min2. Use this corresponding relation:

corresponding(A, B, [A|_], [B|_]).
corresponding(A, B, [_|C], [_|D]) :-
	corresponding(A, B, C, D).
| ?- corresponding(X, 3, [a, b, c], [5, 3, 6]).

X = b ? a

no
| ?-
Member Avatar for TrustyTony

Did you solve it? With smallest or gprolog min_list, the min2 rule is only one line and very obvious logical statement.

Member Avatar for bharatk

Did you solve it? With smallest or gprolog min_list, the min2 rule is only one line and very obvious logical statement.

I actually found a way to solve it & get exactly what I wanted.

Here I check if B is H2 then A is H1. Here is the code:

min2(A,B,[A],[B]).  
min2(A,B,[X|T1],[Y|T2]) :- smallest(W,[Y|T2]), B is W, min2(A,B,T1,T2), !. 
min2(A,B,[H1|T1],[H2|T2]):- B=:=H2 -> A = H1 ; min2(A,B,T1,T2).
Member Avatar for TrustyTony

My version was this, I kind of like the simplicity especially if you utilice gprolog min_list, it is short and simple

corresponding(A, B, [A|_], [B|_]).
corresponding(A, B, [_|C], [_|D]) :- corresponding(A, B, C, D).
min2(A, B, C, D) :- min_list(D, B), corresponding(A, B, C, D).

For min_list implementation, as I posted to StackOverflow (don't double post other time), my smallest with cuts as yours was copy from internet:

% length 1 is base case, all  minimums are equal, so cuts
smallest([A], A).
% shorten by 1 by dropping bigger or equal
smallest([A, B|C], D) :-
	A > B,
	smallest([B|C], D), !.
% cut means this is else branch and need not condition
smallest([A, _|C], D) :-
	smallest([A|C], D).
Member Avatar for TrustyTony

Your code only returns last occurance of minimum pair, not all pairs.

?- min_pair(X,Y,[a,b,c],[5,3,3]).

X = b
Y = 3 ? a

X = c
Y = 3

no
| ?- min2(X,Y,[a,b,c],[5,3,3]).

X = c
Y = 3

yes
| ?-
Edited by TrustyTony because: n/a
Member Avatar for bharatk

My version was this, I kind of like the simplicity especially if you utilice gprolog min_list, it is short and simple

corresponding(A, B, [A|_], [B|_]).
corresponding(A, B, [_|C], [_|D]) :- corresponding(A, B, C, D).
min2(A, B, C, D) :- min_list(D, B), corresponding(A, B, C, D).

For min_list implementation, as I posted to StackOverflow (don't double post other time), my smallest with cuts as yours was copy from internet:

% length 1 is base case, all  minimums are equal, so cuts
smallest([A], A).
% shorten by 1 by dropping bigger or equal
smallest([A, B|C], D) :-
	A > B,
	smallest([B|C], D), !.
% cut means this is else branch and need not condition
smallest([A, _|C], D) :-
	smallest([A|C], D).

This is elegant & efficient and as you said, the solution I had got didn't find all the pairs.


It does take a while to get used to Prolog's way of doing stuff coming from the imperative world. And sorry for the double posting. I thought I could have more views & discussions by doing so.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.