How to return the largest found result?

Question

I have the following facts, which describes the database of a World Cup:

% host(X) <- X is the host country of World Cup
host('South Africa').
% federation (X,Y) <- X is the federation and Y is the numbers of countries in federation X
% qualified for World Cup.
federation('AFC',4).
federation('UEFA', 10).
federation('CAF', 5).
federation('CONMEBOL', 5).
% member_of(X,Y) <- Country Y is member of federation X
member_of('AFC','Australia').
member_of('UEFA', 'England').
member_of('CAF', 'South Africa').
member_of('CONMEBOL','Brazil').
% top(X) <- Country X is top of the World.
top('Brazil').

The question is, how do I find the federation that the number of Countries qualified to World Cup is largest?
What I think I'm gonna do is something like:
solution(X):-federation(X,Y), isMax(Y).
... but I don't know how to implement it yet.

See this for a similar problem: http://stackoverflow.com/questions/27317069/collect-all-minimum-solutions-from-a-backtrackable-predicate — , Feb 04 '15 at 18:37

score 4 · Accepted Answer · answered Feb 03 '15 at 20:45

4

Your question can be reworded as "Find the federation for which there are no other federation with more qualified countries"

That statement can be written in prolog as:

solution(X):-
  federation(X,Y),    % Find the federation for which
  \+((                % there are no
    federation(_, Z), % other federation with
    Z > Y             % more qualified countries
  )).

answered Feb 03 '15 at 20:45

gusbro

22,357
35
46

1

Good answer (not optimal with regards to computational complexity, that's however beside the point), but why the double parenthesis? Not necessary, or am I mistaken? – Feb 04 '15 at 10:35
@Boris: It may be a quirk of SWI, but if there are no spaces between `\+` and a single `(` then SWI will yell about it. So in SWI either add a space between them or put two parenthesis. – gusbro Feb 04 '15 at 13:38
GNU Prolog does the same thing. When the parenthesis is adjoining the `\+` (no space), Prolog sees the parentheses as part of the query functor syntax (`\+( args )`) rather than a statement grouping (`\+ ( queries )`). – lurker Feb 04 '15 at 13:41
I was wondering about the space.... so you don't want the space, and then you have to add the extra pair of parenthesis. Alright. – Feb 04 '15 at 13:52
@Boris: well, yes... for me it's odd. I don't like seeing that space between` \+` and `(`, so I add the extra parenthesis. It's less annoying to **my** eyes ;) – gusbro Feb 04 '15 at 14:05
The `\+` operator in Prolog is a bit of an oddity. I'm not sure I know of other Prolog operators that work with or without a space, but have different behavior in one case versus the other. – lurker Feb 04 '15 at 14:33
A nice feature of this solution is that it generates all of the maximums if there is more than one. – lurker Feb 04 '15 at 17:52

score 1 · Answer 2 · answered Feb 03 '15 at 22:06

1

library(aggregate) offers the appropriate constructs:

solution(X) :- aggregate(max(N,C), federation(C,N), max(_,X)).

?- solution(X).
X = 'UEFA'.

answered Feb 03 '15 at 22:06

CapelliC

59,646
5
47
90

lurker · Answer 3 · 2015-02-07T16:29:39.457

1

I offer here as another variation and won't claim is the best of those offered so far:

solution(X) :- setof(N-F, federation(F, N), L), reverse(L, [_-X|_]).

The setof/3 will gather unique pairs of N-F where F is the federation name, and N is the number of countries in that federation qualified for World Cup. They will be in increasing order according to the natural order of N-F, which is by number N then by F. The reverse puts the largest number first in the list, and [_-X|_] just selects the number from the head of the list.

ADDENDUM

It should be noted that if the data contains more than one maximum result, @gusbro's approach will generate all of them. However, the aggregate method will not. The setof/reverse method above can provide everything in descending order of magnitude, but needs a little extra help if only the maximums are to be picked out:

pick_top([X-F|_], X, F).
pick_top([_|T], X, F) :-
    pick_top(T, X, F).

solution(X) :-
    setof(N-F, federation(F, N), L),
    reverse(L, [C-Fed|T]),
    pick_top([C-Fed|T], C, X).

This will then generate all of the top federations:

federation('AFC',4).
federation('UEFA', 10).
federation('CAF', 5).
federation('CONMEBOL', 5).
federation('PDQ', 10).

| ?- solution(X).

X = 'UEFA' ? ;

X = 'PDQ' ? ;

no

An alternative solution using bagof and avoiding reverse:

pick_top([X-F|T], Top) :-
    pick_top(T, X, [F], Top).
pick_top([X-F|T], X, A, Top) :-
    pick_top(T, X, [F|A], Top).
pick_top([Y-_|T], X, A, Top) :-
    Y < X,
    pick_top(T, X, A, Top).
pick_top([Y-F|T], X, _, Top) :-
    Y > X,
    pick_top(T, Y, [F], Top).
pick_top([], _, Top, Top).

solution(X) :-
    bagof(N-F, federation(F, N), L),
    pick_top(L, X).

Which produces a list of maximums:

| ?- solution(X).

X = ['PDQ','UEFA'] ? a

no

edited Feb 07 '15 at 16:29

answered Feb 04 '15 at 13:44

lurker

56,987
9
69
103

1

Not as efficient as the answer of @CapelliC, but if you don't have `library(aggregate)` (or don't want to use it) still better than the answer by @gusbro. `library(aggregate)` only works for numerical min and max, anyway, while yours will on any `N-F`. – Feb 04 '15 at 14:17
1

@Boris, thanks for the comments. When I run `time` on the `aggregate` solution versus the `setof`/`reverse` solution, the `aggregate` appears to require significantly more inferences. Although, that was testing done on a fairly small data set, and I don't know if that's a good measure of efficiency. – lurker Feb 04 '15 at 14:38
1

At least on SWI-Prolog, a `sort` is always exactly one inference, and a `setof` is a `bagof` + a `sort`. So this might be skewing the results. `library(aggregate)` should do everything in one pass through the backtrackable predicate (I think), while `setof` + `reverse` does that same pass + sorting the list + reversing it. I am certain some problems are faster your way, anyway. And it is more general. – Feb 04 '15 at 15:22
@Boris, thanks for the very helpful comments. I didn't realize the `sort` tallied only one inference. With the data set size I tried (which wasn't very large), all the times were `0.00` so I didn't really have a good metric by which to judge it. – lurker Feb 04 '15 at 15:27
Seeing your edit, you might consider looking at this quesiton and two very helpful answers: http://stackoverflow.com/questions/27317069/collect-all-minimum-solutions-from-a-backtrackable-predicate PS. You can find all maximums in a single pass through the sorted list without too much trouble, or use a custom sort on the results of `bagof` to get a "reversed" list to start with. – Feb 04 '15 at 18:38
@Boris, indeed, now that I have a "patched up" version, I was thinking it might be cleaner to do it from scratch with `bagof` and then have a sort that plucks the top maximum elements. Although the `pick_top` only traverses the list once and having the list presorted makes that predicate simpler. It just offers the choices one at a time. I considered a simple version that presented the results as a list, but wanted something that backtracked instead. Thanks for the link. – lurker Feb 04 '15 at 18:53

How to return the largest found result?

3 Answers3