1% BEGIN LICENSE BLOCK 2% Version: CMPL 1.1 3% 4% The contents of this file are subject to the Cisco-style Mozilla Public 5% License Version 1.1 (the "License"); you may not use this file except 6% in compliance with the License. You may obtain a copy of the License 7% at www.eclipse-clp.org/license. 8% 9% Software distributed under the License is distributed on an "AS IS" 10% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 11% the License for the specific language governing rights and limitations 12% under the License. 13% 14% The Original Code is The ECLiPSe Constraint Logic Programming System. 15% The Initial Developer of the Original Code is Cisco Systems, Inc. 16% Portions created by the Initial Developer are 17% Copyright (C) 2006 Cisco Systems, Inc. All Rights Reserved. 18% 19% Contributor(s): 20% 21% END LICENSE BLOCK 22 23%---------------------------------------------------------------------- 24\chapter{The Integer Sets Library} 25%HEVEA\cutdef[1]{section} 26\label{chapfdsets} 27\index{library!fd_sets|(} 28%---------------------------------------------------------------------- 29 30 31%---------------------------------------------------------------------- 32%\section{Introduction} 33%---------------------------------------------------------------------- 34 35The {\em fd_sets} library is a solver for constraints over the domain 36of finite sets of integers. Unlike {\em conjunto}, it cannot deal with 37sets elements that are not integers. On the other hand, fd_sets is usually 38faster for integer sets than conjunto. 39 40 41 42\section{Ground Integer Sets} 43 44(Ground) integer sets are simply sorted, duplicate-free lists of integers e.g. 45\begin{verbatim} 46 SetOfThree = [1,3,7] 47 EmptySet = [] 48\end{verbatim} 49Lists which contain non-integers, are unsorted or contain duplicates, 50are not sets in the sense of this library. 51 52 53%---------------------------------------------------------------------- 54\section{Set Variables} 55%---------------------------------------------------------------------- 56 57\subsection{Declaring} 58Set variables are variables which can eventually take a ground integer 59set as their value. They are characterized by a lower bound (the set 60of elements that are definitely in the set) and an upper bound (the 61set of elements that may be in the set). A set variable can be 62declared as follows: 63\begin{verbatim} 64 SetVar :: []..[1,2,3,4,5,6,7] 65\end{verbatim} 66If the lower bound is the empty set (like in this case) this can be written as 67\begin{verbatim} 68 SetVar subset [1,2,3,4,5,6,7] 69\end{verbatim} 70If the lower bound is the empty set and the upper bound is a set of 71consecutive integers, one can also declare it like 72\begin{verbatim} 73 intset(SetVar, 1, 7) 74\end{verbatim} 75which is equivalent to the above. 76 77The predicates to declare sets are: 78\begin{description} 79\item[\biptxtrefni{?Set :: ++Lwb..++Upb}{::/2!fd_sets}{../bips/lib/fd_sets/NN-2.html}] 80\index{\::/2@\texttt{::/2}!fd_sets} 81 Set is an integer set within the given bounds 82\item[\biptxtref{intset(?Set, +Min, +Max)}{intset/3}{../bips/lib/fd_sets/intset-3.html}] 83 Set is a set containing numbers between Min and Max 84\item[\biptxtref{intsets(?Sets, ?N, +Min, +Max)}{intsets/4}{../bips/lib/fd_sets/intsets-4.html}] 85 Sets is a list of N sets containing numbers between Min and Max 86\end{description} 87 88 89 90\subsection{Printing} 91 92Set variables are by default printed in a particular way, e.g. 93\begin{verbatim} 94?- X :: [2,3]..[1,2,3,4], write(X). 95X{[2, 3] \/ ([] .. [1, 4]) : _308{[2 .. 4]}} 96\end{verbatim} 97The curly brackets contain 98\begin{enumerate} 99\item the lower bound of the set 100\item the union symbol 101\item the set of optional values (that may or may not be in the set) 102\item a colon 103\item a finite domain indicating the admissible cardinality for the set 104\end{enumerate} 105 106 107 108\subsection{Domain Access} 109 110\begin{description} 111\item[\biptxtref{potential_members(?Set, -List)}{potential_members/2}{../bips/lib/fd_sets/potential_members-2.html}] 112 List is the list of elements of whose membership in Set is currently uncertain 113\item[\biptxtref{set_range(?Set, -Lwb, -Upb)}{set_range/3}{../bips/lib/fd_sets/set_range-3.html}] 114 Lwb and Upb are the current lower and upper bounds on Set 115\end{description} 116 117 118%---------------------------------------------------------------------- 119\section{Constraints} 120%---------------------------------------------------------------------- 121 122\subsection{Membership} 123 124\begin{description} 125\item[\biptxtrefni{?X in ?Set}{in/2!fd_sets}{../bips/lib/fd_sets/in-2.html}] 126\index{in/2@\texttt{in/2}!fd_sets} 127 The integer X is member of the integer set Set 128\item[\biptxtrefni{?X notin ?Set}{notin/2!fd_sets}{../bips/lib/fd_sets/notin-2.html}] 129\index{notin/2@\texttt{notin/2}!fd_sets} 130 The integer X is not a member of the integer set Set 131\item[\biptxtrefni{membership_booleans(?Set, ?BoolArr)}{membership_booleans/2!fd_sets}{../bips/lib/fd_sets/membership_booleans-2.html}] 132\index{membership_booleans/2@\texttt{membership_booleans/2}!fd_sets} 133 BoolArr is an array of booleans describing Set 134\end{description} 135 136 137\subsection{Cardinality} 138 139\begin{description} 140\item[\biptxtrefni{\#(?Set, ?Card)}{\#/2!fd_sets}{../bips/lib/fd_sets/H-2.html}] 141\index{\#/2@\texttt{\#/2}!fd_sets} 142 Card is the cardinality of the integer set Set 143\end{description} 144 145 146\subsection{Set Relations} 147 148\begin{description} 149 150\item[\biptxtrefni{difference(?Set1, ?Set2, ?Set3)}{difference/3!fd_sets}{../bips/lib/fd_sets/difference-3.html}] 151\index{difference/3@\texttt{difference/3}!fd_sets} 152 Set3 is the difference of the integer sets Set1 and Set2 153 154\item[\biptxtrefni{?Set1 disjoint ?Set2}{disjoint/2!fd_sets}{../bips/lib/fd_sets/disjoint-2.html}] 155\index{disjoint/2@\texttt{disjoint/2}!fd_sets} 156 The integer sets Set1 and Set2 are disjoint 157 158\item[\biptxtrefni{?Set1 includes ?Set2}{includes/2!fd_sets}{../bips/lib/fd_sets/includes-2.html}] 159\index{includes/2@\texttt{includes/2}!fd_sets} 160 Set1 includes (is a superset) of the integer set Set2 161 162\item[\biptxtrefni{intersection(?Set1, ?Set2, ?Set3)}{intersection/3!fd_sets}{../bips/lib/fd_sets/intersection-3.html}] 163\index{intersection/3@\texttt{intersection/3}!fd_sets} 164 Set3 is the intersection of the integer sets Set1 and Set2 165 166\item[\biptxtrefni{?Set1 sameset ?Set2}{sameset/2!fd_sets}{../bips/lib/fd_sets/sameset-2.html}] 167\index{sameset/2@\texttt{sameset/2}!fd_sets} 168 The sets Set1 and Set2 are equal 169\item[\biptxtrefni{?Set1 subset ?Set2}{subset/2!fd_sets}{../bips/lib/fd_sets/subset-2.html}] 170\index{subset/2@\texttt{subset/2}!fd_sets} 171 Set1 is a subset of the integer set Set2 172\item[\biptxtrefni{symdiff(?Set1, ?Set2, ?Set3)}{symdiff/3!fd_sets}{../bips/lib/fd_sets/symdiff-3.html}] 173\index{symdiff/2@\texttt{symdiff/2}!fd_sets} 174 Set3 is the symmetric difference of the integer sets Set1 and Set2 175\item[\biptxtrefni{union(?Set1, ?Set2, ?Set3)}{union/3!fd_sets}{../bips/lib/fd_sets/union-3.html}] 176\index{union/2@\texttt{union/2}!fd_sets} 177 Set3 is the union of the integer sets Set1 and Set2 178\end{description} 179 180 181\subsection{N-ary Set Relations} 182 183\begin{description} 184\item[\biptxtref{all_disjoint(+Sets)}{all_disjoint/1}{../bips/lib/fd_sets/all_disjoint-1.html}] 185 Sets is a list of integers sets which are all disjoint 186\item[\biptxtref{all_union(+Sets, ?SetUnion)}{all_union/2}{../bips/lib/fd_sets/all_union-2.html}] 187 SetUnion is the union of all the sets in the list Sets 188\item[\biptxtref{all_intersection(+Sets, ?SetIntersection)}{all_intersection/2}{../bips/lib/fd_sets/all_intersection-2.html}] 189 SetIntersection is the intersection of all the sets in the list Sets 190\end{description} 191 192 193\subsection{Set Weights} 194 195\begin{description} 196\item[\biptxtref{weight(?Set, ++ElementWeights, ?Weight)}{weight/3}{../bips/lib/fd_sets/weight-3.html}] 197 According to the array of element weights, the weight of set Set1 is Weight 198\end{description} 199 200 201%---------------------------------------------------------------------- 202\section{Set Expressions} 203%---------------------------------------------------------------------- 204 205In most positions where a set or set variable is expected one can also 206use a set expression. A set expression is composed from ground sets 207(integer lists), set variables, and the following set operators: 208\begin{verbatim} 209 Set1 /\ Set2 % intersection 210 Set1 \/ Set2 % union 211 Set1 \ Set2 % difference 212\end{verbatim} 213When such set expressions occur, they are translated into auxiliary 214\bipref{intersection/3}{../bips/lib/fd_sets/intersection-3.html}, 215\bipref{union/3}{../bips/lib/fd_sets/union-3.html} and 216\bipref{difference/3}{../bips/lib/fd_sets/difference-3.html} 217constraints, respectively. 218 219 220%---------------------------------------------------------------------- 221\section{Search Support} 222%---------------------------------------------------------------------- 223 224The 225\bipref{insetdomain/4}{../bips/lib/fd_sets/insetdomain-4.html} 226predicate can be used to enumerate all ground instantiations of a set 227variable, much like 228\bipref{indomain/1}{../bips/lib/fd/indomain-1.html} 229in the finite-domain case. 230 231\begin{description} 232\item[\biptxtref{insetdomain(?Set, ?CardSel, ?ElemSel, ?Order)}{insetdomain/4}{../bips/lib/fd_sets/insetdomain-4.html}] 233 Instantiate Set to a possible value 234\end{description} 235 236 237%---------------------------------------------------------------------- 238\section{Example} 239%---------------------------------------------------------------------- 240 241The following program computes so-called Steiner triplets. 242These are triplets of numbers from 1 to N such that 243any two triplets have at most one element in common. 244\begin{verbatim} 245:- lib(fd_sets). 246:- lib(fd). 247 248steiner(N, Sets) :- 249 NB is N * (N-1) // 6, % compute number of triplets 250 intsets(Sets, NB, 1, N), % initialise the set variables 251 ( foreach(S,Sets) do 252 #(S,3) % constrain their cardinality 253 ), 254 ( fromto(Sets,[S1|Ss],Ss,[]) do 255 ( foreach(S2,Ss), param(S1) do 256 #(S1 /\ S2, C), % constrain the cardinality 257 C #<= 1 % of pairwise intersections 258 ) 259 ), 260 label_sets(Sets). % search 261 262label_sets([]). 263label_sets([S|Ss]) :- 264 insetdomain(S,_,_,_), 265 label_sets(Ss). 266\end{verbatim} 267Here is an example of running this program 268\begin{verbatim} 269?- steiner(9,X). 270 271X = [[1, 2, 3], [1, 4, 5], [1, 6, 7], [1, 8, 9], 272 [2, 4, 6], [2, 5, 8], [2, 7, 9], [3, 4, 9], 273 [3, 5, 7], [3, 6, 8], [4, 7, 8], [5, 6, 9]] More? (;) 274\end{verbatim} 275 276\index{library!fd_sets|)} 277 278%HEVEA\cutend 279