ijd@otter.hple.hp.com (Ian Dickinson) (03/26/88)
This is a little problem that I encountered today, that, whilst I have thought of a number of solutions, none of them seem to be very neat or particularly efficient. Here is the problem... Assume a relation "Y is contained in X", specified as: contains( ?X, ?Y ). Assume also, two global predicates p/1 and q/1. (As is always the case in these problems, p and q are expensive to compute :-). The problem is to define a predicate exactly_one/2: exactly_one( +X, ?Y ) is true if X contains Y, Y satisfies p/1 and all of the other Y' contained by X satisfy q/1. Any offers? Thanks in advance, Ian. +-------------------------------------------------------------------------+ |Ian Dickinson, Hewlett Packard Laboratories, Bristol, England| |net: ijd@hplb.uucp ijd%idickins@hplabs.HP.COM ..!mcvax!ukc!hplb!ijd| |"I've been to every single book I know +-------------------+ | To soothe the thoughts that plague me so" -Sting | voice: 0272-799910| |Nevertheless, my opinions are entirely my own fault | | +-----------------------------------------------------+-------------------+
matthew@maui.cs.ucla.edu (Matthew Merzbacher) (03/27/88)
In article <1600011@otter.hple.hp.com> ijd@otter.hple.hp.com (Ian Dickinson) writes: > >Here is the problem... > >Assume a relation "Y is contained in X", specified as: > contains( ?X, ?Y ). > >Assume also, two global predicates p/1 and q/1. (As is always the case in >these problems, p and q are expensive to compute :-). > >The problem is to define a predicate exactly_one/2: > > exactly_one( +X, ?Y ) > is true if X contains Y, Y satisfies p/1 and all of the other > Y' contained by X satisfy q/1. > >Any offers? > Is this really supposed to be exactly_one? If so, then you want a restriction that none of the Y' satisfy p/1. Of course, you could just have a negation of p/1 as the first condition of q/1 to achieve this given the above definition. First, a little proof: Define CX as the cardinality (number of members) of X, CY as the cardinality of Y, and CY' as the cardinality of Y' ________ THM: If exactly_one succeeds, then q/1 will be executed AT LEAST CY' times and p/1 will be executed AT LEAST once. This is clear since you have to find the Y which will satisfy p/1 and you must also presumably check all the other Y' to make sure they satisfy q/1. ________ Now, since CY' = CX - 1, and since we need to make CY' calls to q/1 we may make CX calls to q/1 without worrying too much more about efficiency (one extra call). Having made these calls, one of three possibilities will be true: 1. All q/1 will succeed 2. All but 1 q/1 will succeed 3. At least 2 q/1 will fail In the first case, we must go on to check each potential Y in X to find one that satisfies p/1. If there is only one, then this step will take (on average) CX/2 calls to p/1. The worst case is, of course CX, and the best case is 1 (first try). In case 2, as soon as q/1 fails, we should check to see if the offending Z satisfies p/1 if it does, then we have found Y and we must check the remaining Y' to determine if they satisfy q/1. If the offending Z does not satisfy p/1, then the algorithm fails, since we have found a Z in X which is neither Y nor in Y'. If Z satisfies p/1 and the check of the remaining unchecked member of Y' reveals a failure, then exactly_once fails. --- Thumbnail Analysis: 1. All q/1 will succeed -- Takes CX calls to q/1 + CX/CY (on average) calls to p/1 This is becuase all of X is checked for a candidate Y (calls to q/1). Finding none, each member of X must be checked until one satisfies p/1. Assuming the CY possible Y are evenly distributed over X, the second step will take CX/CY calls to p/1 2. All but 1 q/1 will succeed -- Takes CX calls to q/1 + 1 call to p/1 The CX calls are made since we must check all q/1 to find the only one which does not succeed. It must therefore be Y and satisfy p/1. If it does not satisfy p/1, then the algorithm takes only (on average) CX/2 calls to q/1 + 1 call to p/1. 3. At least 2 q/1 will fail -- Takes (on average) 2*CX/N+1 calls to q/1 + 1 call to p/1 -- (N is the number of members of X which fail q/1) Actually, it's better than this. We make calls to q/1 until failure occurs. When the failure occurs, if p/1 fails on that candidate, then we are done (in CX/N calls to q/1 + 1 call to p/1). On the other hand, if p/1 succeeds, then we must continue checking using q/1 until another failure. Notice that if N=1 then this degenerates to case #2. Thus, in the two cases where there is at least one Z in X which does not satisfy q/1, my algorithm makes the minimum number of calls. In the case where all X satisfy q/1, my algorithm must make CX/2 calls more than minimum. However, I maintain that this is unavoidable by any algorithm, though I can't seem to prove it. ========= STOP HERE - Only the bold go further and many will not return. Although I shudder at the thought of posting code because my style is so bad, here's a shot. My Algorithm: % find_Z(+List, -Z, -Remainder) looks through the list of candidates and returns % the first Z which does not satisfy q/1. It also returns the remainder of the % list of candidates. If all candidates satisfy q/1, then find_Z fails. find_Z([],_,[]) :- !, fail. find_Z([Candidate|Rest], Z, Remainder) :- q(Candidate), find_Z(Rest,Z,Remainder). find_Z([Z|Remainder],Z,Remainder). % find_Y(+List,-Y) looks through the list (which is X originally) and finds a % member which satisfies p/1. If no member satisfies p/1 then find_Y fails. find_Y([],_) :- !, fail. find_Y([Candidate|Rest], Candidate) :- p(Candidate). find_Y([_|Rest], Y) :- find_Y(Rest, Y). % exactly_one(+X,-Y) uses find_Z/3 to check each member of X to find one that % does not satisfy q/1. If any Y of X do not satisfy q/1 then Y must satisfy % p/1 and all remaining X must satisfy q/1. If all X satisfy q/1 then at least % one Y of X must satisfy p/1 exactly_one(X, Y) :- find_Z(X, Y, Remainder), !, p(Y), not(find_Z(Remainder,_,[])). exactly_one(X, Y) :- find_Y(X, Y). Matthew Merzbacher ARPA: matthew@CS.UCLA.EDU 4 line signature UUCP: ...!{cepu|ihnp4|sdcrdcf|ucbvax}!ucla-cs!matthew limit is retarded NOTENET: ...!bach%mozart!matthew@beethoven
ok@quintus.UUCP (Richard A. O'Keefe) (03/27/88)
In article <1600011@otter.hple.hp.com>, ijd@otter.hple.hp.com (Ian Dickinson) writes: > Assume a relation "Y is contained in X", specified as: > contains( ?X, ?Y ). > Assume also, two global predicates p/1 and q/1. (As is always the case in > these problems, p and q are expensive to compute :-). > The problem is to define a predicate exactly_one/2: > exactly_one( +X, ?Y ) > is true if X contains Y, Y satisfies p/1 and all of the other > Y' contained by X satisfy q/1. Let's start like this: exactly_one(X, Y) :- setof(Z, contains(X, Z), Zs), p_and_qs(Y, Zs). This much is straightforward. In the context of your actual problem, it may be easy to compute Zs directly. The tricky thing is p_and_qs. You do not say whether it is possible for p/1 and q/1 to be true of the same term. There are three cases: 1. there is exactly one element Z of Zs for which q(Z) is false and p(Z) is true of that Z. In this case Y=Z. 2. q(Z) is true of every element Z of Zs, and p(Z) is true of at least one such Z. This this case, Y is any of the Zs for which p(Y). 3. There is no solution for Y. In order to tell which of the first two cases we've got, we'll write a predicate to return the longest suffix of Zs whose head does not satisfy q/1, or the empty list if every element of Zs satisfies q/1. Then if we get a non-empty list, p must be true of the first element and q of all the rest. If we get an empty list, any member of Zs which satisfies p/1 will do. p_and_qs(Y, Zs) :- first_non_q(Zs, RestZs), p_and_qs(RestZs, Y, Zs). first_non_q([Z|Zs], RestZs) :- q(Z), !, first_non_q(Zs, RestZs). first_non_q(RestZs, RestZs). p_and_qs([Y|Qs], Y, _) :- p(Y), first_non_q(Qs, []). p_and_qs([], Y, Zs) :- member(Y, Zs), p(Y). This checks q(Z) once for each Z, and checks p(Y) either once or once for each Z unifying with Y. Without more information about p and q I don't think this can be reduced. I have tested this code. It can solve for X as well as Y.
sfk@otter.hple.hp.com (Stephen Knight) (03/28/88)
Dear Ian,
Here is my solution, which I submit for elegance points ...
exactly_one( X, Y ) :-
X contains Y, /* contains is infix in my version */
p( Y ),
forall(
( X contains Y1, Y /= Y1 ),
q( Y1 )
).
forall( X, Y ) :- not( (X, not(Y)) ).
The inefficiency of this programs is the repeated calculation of q( Term ).
One approach would be to patch this by making "q" cache, but other solutions
on this problem are more efficient than that anyway.
Steve Knight
PS: I have tested this on some simple examples, although I could have introduced
errors in transcribing it to this message.lee@mulga.oz (Lee Naish) (03/30/88)
In article <1600011@otter.hple.hp.com> ijd@otter.hple.hp.com (Ian Dickinson) writes: > exactly_one( +X, ?Y ) > is true if X contains Y, Y satisfies p/1 and all of the other > Y' contained by X satisfy q/1. % NU-Prolog solution (will generate X or Y or both) exactly_one(X, Y) :- solutions(Y0, X contains Y0, YList), % like setof delete(Y, YList, Remainder), p(Y), all Y1 member(Y1, Remainder) => q(Y1). % any formatting ideas? lee
ok@quintus.UUCP (Richard A. O'Keefe) (03/31/88)
In article <2644@mulga.oz>, lee@mulga.oz (Lee Naish) writes: : In article <1600011@otter.hple.hp.com> ijd@otter.hple.hp.com (Ian Dickinson) writes: : > exactly_one( +X, ?Y ) : > is true if X contains Y, Y satisfies p/1 and all of the other : > Y' contained by X satisfy q/1. : : % NU-Prolog solution (will generate X or Y or both) : exactly_one(X, Y) :- : setof(Y0, X contains Y0, YList), % <edited> : select(Y, YList, Remainder), % <edited> : p(Y), : forall(member(Y1, Remainder), q(Y1)). % <edited> {Note: I have edited some of the lines not to "improve" the code but to make it easier for people such as myself who haven't got a copy of NU Prolog to try this solution. This version _behaves_ like Lee Naish's original, but his code has claims to being logic. } This is much prettier than my solution, but it doesn't do quite the same thing. Recall that the original posting said that p/1 and q/1 were to be thought of as very expensive, so the goal is to minimize the number of calls to p/1 and q/1. My code, as you will recall, as exactly_one(X, Y) :- setof(Z, contains(X,Z), Zs), first_non_q(Zs, RestZs), p_and_qs(RestZs, Y, Zs). first_non_q([Z|Zs], RestZs) :- | first_non_q([], []). q(Z), | first_non_q([Z|Zs], U) :- !, | if q(Z) then first_non_q(Zs, RestZs).| first_non_q(Zs, U) first_non_q(RestZs, RestZs). | else U = [Z|Zs]. p_and_qs([Y|Qs], Y, _) :- | p_and_qs([Y|Qs], Y, _) :- p(Y), | p(Y), first_non_q(Qs, []). | all Q member(Q,Qs) => q(Q). p_and_qs([], Y, Zs) :- | p_and_qs([], Y, Zs) :- member(Y, Zs), | member(Y, Zs), p(Y). | p(Y). As the right column shows (if I've got it right), a pure version is possible. The algorithms are different. It is interesting to see how often they call p/1 and q/1 in various cases. I assume that all solutions of exactly_one/2 are being found by backtracking. p OK q OK p LN q LN situation ---- ---- ---- ---- ---------------- N N N N*(N-1) p(Y),q(Y) true for all Y 1 N N N-1 p(Y<I>), q(Y) for all Y but Y<I> 1 2 N N ~q(Y<1>), ~q(Y<2>) 1 N N N*(N-2)+2 q(Y) for all Y but Y<N-1>,Y<N-2> If the caller commits to the first solution, Lee Naish's code will call p/1 less often, and will call q/1 at most N-1 times, but in that context my code will call q/1 N times and p/1 at most once. Another illustration of the difference between specifications and programs, alas.
voda@ubc-cs (Paul Voda) (04/01/88)
In article <839@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: >: > exactly_one( +X, ?Y ) >: > is true if X contains Y, Y satisfies p/1 and all of the other >: > Y' contained by X satisfy q/1. >: >: % NU-Prolog solution (will generate X or Y or both) >: exactly_one(X, Y) :- >: setof(Y0, X contains Y0, YList), % <edited> >: select(Y, YList, Remainder), % <edited> >: p(Y), >: forall(member(Y1, Remainder), q(Y1)). % <edited> > The code of Naish as edited by O'Keefe contains three list constructions/traversals: setof, forall, and select. One list operation is sufficient provided that your Prolog has a LOGICAL "all solutions" predicate ( i.e. the one looking for an ORDERED list with no repetitions of values satisfying a formula). Since I do not have such a Prolog and anyway I program mostly in Trilogy here is the solution in Trilogy: Aux = Some_notP1Q | P1_of(B) | Some_Q proc Exactly_one(x:<A, y:>B) iff all aux in listaux Contains(x,z) & if P1(z) then aux = P1_of(z) elsif Q(z) then aux = Some_Q else aux = Some_notP1Q end end & listaux = P1_of(y),w & ( w = Nil | w = Some_Q,Nil ) Assumptions: For simplicity sake (without compromising the generality of the solution) I assume the following about the predicates Contains, P, and Q. Actually I use P1 since P is a predefined identifier in Trilogy.: P1 and Q may hold for the same x. The declarations are as follows: pred Contains(x:<A,y:>B) {output B's are contained in input (given)A} proc P1(x:<B) {input x of type B satisfies P1} proc Q1(x:<B) {input x of type B satisfies Q} Explanation: 1) The all-solutions construct "all" constructs a sorted list without repetitions called listaux (of type "list Aux") containing only and all aux's (of type Aux) such that the formula Contains(x,z) .... w = Some_Q) holds for some "z". 2) The type Aux is a union type (corresponding to two atoms and one functor of Prolog). The ordering on Aux in Trilogy is automatically derived from the ordering of the domain U of Trilogy as follows: Some_notP1Q < P1_of(b1) < P1_of(b2) < Some_Q for all B's: b1 < b2. 3) The "all" solutions bactracks through the predicate Contains to obtain all z's contained in x. For each z a value aux is constructed according to whether P1, Q1 (and not P1), or not P1 not Q holds of z. 4) After the list listaux has been constructed the predicate Exactly_one succeeds iff i) listaux is non_empty, ii) listaux starts with a P1_of(y); i.e. P1(y) holds and there is no z contained in x such that not P1(z) and not Q(z). iii) listaux contains either one element, or if two then the second one is Some_Q, i.e. no other z contained in x satisfies P1. 5) The or (|) at the end of the predicate Exactly_one is compiled without a choice point, just as a boolean or in Pascal.