%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%% The {log} library %%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%% version 4.5 %%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % May 2005 - by Gianfranco Rossi % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %This file contains the {log} definition of those operations on %sets which are not provided as constraints in {log}. It can be %loaded into the {log} environment by issuing the goal %consult(lib) (provided 'setloglib.slog' is the name you give %to this file). %The predicates defined in this file are: % % - powerset/2 % - cross_product/3 % - list_to_set/2 % - bag_to_set/2 % - int_to_set/2 % - int_to_bag/2 % - diff1/3 % - msize/2 % %This file provides also alternative definitions for some of the %basic set predicates, aimed at reducing the number of repeated solutions. %The list of these predicates is % % - xless/3 % - xsubset/2 % - xun/3 % - xint/3 % - xdiff/3 % - xndiff/3 % - xsdiff/3 % - xsize/2 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% powerset(S,PS) :- % powerset(+S,?PS) is true if PS is the powerset PS = {SS : subset(SS,S)}. % of S (i.e., PS = 2^S) cross_product(A,B,CP) :- % cross_product(+A,+B,?CP) is true if CP is the CP = {X : exists([Y,Z], % Cartesian product of sets A and B X = {Y,Z} & Y in A & Z in B)}. list_to_set([],{}). % list_to_set(+L,?S) is true if S denotes the set list_to_set([X|L],{X\S}) :- % of all elements of the list L list_to_set(L,S). bag_to_set({},{}). % bag_to_set(+M,?S) is true if S denotes the set bag_to_set(M,{X\S}) :- % of all elements of the multiset M (M = *{X\R})! & bag_to_set(R,S). int_to_set(int(A,B),{}) :- % int_to_set(+I,?S) is true if S denotes the set A > B. % of all elements of the interval I int_to_set(int(A,B),{A\S}) :- A =< B & A1 is A + 1 & int_to_set(int(A1,B),S). int_to_bag(int(A,B),{}) :- % int_to_bag(+I,?M) is true if M denotes the multiset A > B. % of all elements of the interval I int_to_bag(int(A,B),*{A\M}) :- A =< B & A1 is A + 1 & int_to_bag(int(A1,B),M). diff1({X\S},X,S) :- % diff1(?S,?X,?R) equivalent to diff(S,{X},R) X nin S. % but more efficient diff1(S,X,S) :- X nin S. msize(S,N) :- in_msize(S,0,N). % msize(?S,?N) is true if N is the cardinality in_msize({},N,N). % of the multiset S (i.e., N = |S|) in_msize(*{_\SS},N,M) :- N neq M & NN is N + 1 & in_msize(SS,NN,M). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %The following predicates provide %an improved implementation of the basic set-theoretic operations %that reduces the number of repeated equivalent solutions %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% xless(S,X,SS) :- % remove the element X from S, if S is ground test(ground(S),R) & % otherwise, remove any element X from S (R=true & less(S,X,SS)! or R=false & less(S,X,SS)). xsubset(S1,S2) :- % subset (S1 \subseteq S2) test(ground(S),R) & (R=true & xxsubset(S1,S2) or R=false & subset(S1,S2)). xxsubset({},S2). xxsubset(S1,S2) :- less(S1,X,SS1)! & call(X in S2) & xxsubset(SS1,S2). xun(R,S,U) :- % union (T = R \cup S) test(ground(R),H) & (H=true & xxun(R,S,U) or H=false & un(R,S,U)). xxun('{}',X,X). xxun(R,S,{X\U}) :- less(R,X,RR)! & X nin S & xxun(RR,S,U). xxun(R,S,U) :- less(R,X,RR)! & call(X in S) & xun(RR,S,U). xint(R,S,U) :- % intersection (T = R \cap S) test(ground(R),H) & (H=true & xxint(R,S,U) or H=false & int(R,S,U)). xxint({},_,{}). xxint(R,S,{X\U}) :- less(R,X,RR)! & call(X in S) & xxint(RR,S,U). xxint(R,S,T) :- less(R,X,RR)! & X nin S & xxint(RR,S,T). xdiff(R,S,U) :- % difference (T = R \setminus S) test(ground(R),H) & (H=true & xxdiff(R,S,U) or H=false & diff(R,S,U)). xxdiff({},_,{}). xxdiff(R,S,T) :- less(R,X,RR)! & call(X in S) & xxdiff(RR,S,T). xxdiff(R,S,{X\U}) :- less(R,X,RR)! & X nin S & xxdiff(RR,S,U). xndiff(R,S,T) :- % not difference (T = R \not\setminus S) xdiff(R,S,T1) & T1 neq T. xsdiff(R,S,T) :- % symmetric difference (T = R \triangle S) xdiff(R,S,A) & xdiff(S,R,B) & xun(A,B,T). xsize(S,N) :- size(S,N). % for compatibility with previous releases %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% test(Pred,Res) :- prolog_call((call(Pred),!,Res=true ; Res=false)). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% setlog_lib_help :- nl & write('Available {log} library predicates:') & nl & nl & write('powerset(+S,?PS): powerset (PS = 2^S)') & nl & write('cross_product(+A,+B,?CP): the Cartesian product of sets A and B') & nl & write('list_to_set(+L,?S): S is the set of all elements of the list L') & nl & write('bag_to_set(+M,?S): S is the set of all elements of the bag M') & nl & write('int_to_set(+I,?S): S is the set of all elements of the interval I') & nl & write('int_to_bag(+I,?M): M is the multiset of all elements of the interval I') & nl & write('diff1(?S,?X,?R): equivalent to diff(S,{X},R) but more efficient') & nl & write('msize(?S,?N): multiset cardinality (N = |S|)') & nl & setlog_lib_help2. setlog_lib_help2 :- nl & write('The {log} library provides also alternative definitions for some ') & nl & write('set predicates, aimed at reducing the number of repeated solutions.') & nl & nl & write('xless/3') & nl & write('xsubset/2') & nl & write('xun/3') & nl & write('xint/3') & nl & write('xdiff/3') & nl & write('xndiff/3') & nl & write('xsdiff/3') & nl & write('xsize/2') & nl.