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