15.6.2 Finite Set Selection Constraints

We discuss three versions of set selection constraints.

Syntax and Semantics

The first version is similar to the element constraint except that we now select an element from a list of finite sets (instead of a list of integers).

$S = \langle S_1,\ldots,S_n \rangle[Y]$

The variables $S, S_1,\ldots,S_n$ denote finite sets of integers whereas has type integer. The constraint is equivalent to

$S = S_Y \wedge Y \in \{1,\ldots,n\}$

There are more powerful variants of set selection constraints. One can select a subset of elements of a list and apply a set operator to them. The variant for the union operator has the following form:

$S = \cup \langle S_1,\ldots,S_n \rangle[S_0]$

All variables $S, S_1,\ldots,S_n, S_0$ denote finite sets of integers and may be restricted further by finite set constraints. This selection constraint is equivalent to

$S = \cup\{ S_X \mid X \in S_0\} \wedge S_0\subseteq \{1,\ldots,n\}$

i.e. it says that is the union of all those elements S_X in the $S_1,\ldots,S_n$ whose index belongs to S_0 .

There exists an analogous selection constraint which employs the intersection instead of the union operator.

$S = \cap \langle S_1,\ldots,S_n \rangle[S_0]$

Example

This example illustrates the propagation behaviour of the first of the above set selection constraints.

declare [Select]={Module.link ['x-ozlib://duchier/cp/Select.ozf']} declare S1 = {FS.value.make [5]} declare S2 = {FS.value.make [1 21]} declare S3 = {FS.value.make [1 77]} declare I = {FD.decl} declare S = {Select.fs [S1 S2 S3] I} {Browse S} {Browse I}

When feeding this code to the Oz Emulator the browser displays:

%% S{{}..{1 5 21 77}}#{1#2} %% I{1#3}

This means that $\emptyset \subseteq S \subseteq \{1,5,21,77\}$ , ${\rm card}(S)\in \{1,2\}$ and $I \in \{1,2,3\}$ . Next, lets feed the following constraint in addition:

{FS.exclude 5 S}

The Browse now updates its output to:

% S{{1}..{1 21 77}}#2 % I{2#3}

Since the first set contributes 5 which does not belong to does the first set cannot be selected so that $I \not= 1$ . Thus, either the second or third set must be selected. Since both of them have cardinality 2 this must also hold for . Furthermore, must be a subset of both sets and thus subsumed by $\{1, 21, 77\}$ .