CODEWITHSUNDEEP
prolog
brian seo
brian seo

Reputation: 11

prolog finding max from a list of facts

Hi sorry I'm really new to Prolog. Say I have a list of facts say 6 facts the first column of numbers represents the persons ID, and the second column represents the number of wins a person has. If I want to find the person with the most wins how would I go about doing this?

wins(1, 22).
wins(2, 24).
wins(3, 23).
wins(4, 20).
wins(5, 21).
wins(6, 19).

something like that? lol to be honest, I don't really know what I'm doing

X = wins(_, Xs) 
Y = wins(_, Ys)
most wins(X) :- Xs > Ys

Upvotes: 1

Views: 1997

Answers (1)

CapelliC
CapelliC

Reputation: 60034

There is more than a way to obtain that info.

most_wins(Id) :-
    wins(Id, W), \+ (wins(_, W1), W1 > W).

or, if your Prolog has library(aggregate) :-

most_wins(Id) :-
    aggregate(max(W, Id), wins(Id, W), max(_, Id)).

or you could use setof/3

most_wins(Id) :-
    setof(N-Id, W^(wins(Id, W), N is -W), [_-Id|_]).

There are obvious speed/memory trade-offs: the first way it's memory efficient, O(1), but time complexity is O(N^2), because it scans 2 times the set of candidates. Second and third are (I think) practically equivalent, under current implementation in SWI-prolog, both build the list of candidates (then are O(N) in space) and then select the element - O(N log N) in time.

Go with the first if the candidates are facts.

edit Yet another way, the better from the efficiency viewpoint, make use of non-backtrackable assignment. Just scan the candidates, keeping the max on the go. Plain Prolog will require assert/retract to perform such task, making it rather inefficient. But many Prologs have more efficient ways to store 'global' variables...

Upvotes: 2

Related Questions