1

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  

1 Answer 1

2

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.