Path: utzoo!utgpu!water!watmath!clyde!rutgers!ucla-cs!maui!matthew From: matthew@maui.cs.ucla.edu (Matthew Merzbacher) Newsgroups: comp.lang.prolog Subject: Re: Programming Quickie Message-ID: <10652@shemp.CS.UCLA.EDU> Date: 26 Mar 88 21:04:43 GMT References: <1600011@otter.hple.hp.com> Sender: news@CS.UCLA.EDU Reply-To: matthew@maui.UUCP (Matthew Merzbacher) Organization: UCLA Computer Science Department Lines: 139 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