10.4  Constraints

The constraints that ic_sets implements are the usual relations over sets. The membership (in/2, notin/2) and cardinality constraints (#/2) establish relationships between set variables and integer variables:

---

?X in ?Set The integer X is member of the integer set Set ?X notin ?Set The integer X is not a member of the integer set Set #(?Set, ?Card) Card is the cardinality of the integer set Set

Figure 10.2: Membership and Cardinality Constraints

---

?- X ::[]..[1, 2, 3], 2 in X, 3 in X, #(X, 2).
X = [2, 3]
Yes (0.01s cpu)

?- X :: []..[1, 2, 3, 4], 3 in X, 4 notin X.
X = X{[3] \/ ([] .. [1, 2]) : _2161{1 .. 3}}
Yes (0.00s cpu)

Possible constraints between two sets are equality, inclusion/subset and disjointness:

?- X subset [1, 2, 3, 4].
X = X{([] .. [1, 2, 3, 4]) : _2139{0 .. 4}}
Yes (0.00s cpu)

?- X :: []..[1, 2, 3, 4], Y :: []..[3, 4, 5, 6], X subset Y.
X = X{([] .. [3, 4]) : _2176{0 .. 2}}
Y = Y{([] .. [3, 4, 5, 6]) : _2367{0 .. 4}}
There are 4 delayed goals.
Yes (0.00s cpu)

?- X :: [2] .. [1, 2, 3, 4], Y :: [3] .. [1, 2, 3, 4], X disjoint Y.
X = X{[2] \/ ([] .. [1, 4]) : _2118{1 .. 3}}
Y = Y{[3] \/ ([] .. [1, 4]) : _2213{1 .. 3}}
There are 2 delayed goals.
Yes (0.00s cpu)

---

?Set1 sameset ?Set2 The sets Set1 and Set2 are equal ?Set1 disjoint ?Set2 The integer sets Set1 and Set2 are disjoint ?Set1 includes ?Set2 Set1 includes (is a superset) of the integer set Set2 ?Set1 subset ?Set2 Set1 is a (non-strict) subset of the integer set Set2 intersection(?Set1, ?Set2, ?Set3) Set3 is the intersection of the integer sets Set1 and Set2 union(?Set1, ?Set2, ?Set3) Set3 is the union of the integer sets Set1 and Set2 difference(?Set1, ?Set2, ?Set3) Set3 is the difference of the integer sets Set1 and Set2 symdiff(?Set1, ?Set2, ?Set3) Set3 is the symmetric difference of the integer sets Set1 and Set2

Figure 10.3: Basic Set Relations

---

Possible constraints between three sets are for example intersection, union, difference and symmetric difference. For example:

?- X :: [2, 3] .. [1, 2, 3, 4],
   Y :: [3, 4] .. [3, 4, 5, 6],
   ic_sets : intersection(X, Y, Z).
X = X{[2, 3] \/ ([] .. [1, 4]) : _2127{2 .. 4}}
Y = Y{[3, 4] \/ ([] .. [5, 6]) : _2222{2 .. 4}}
Z = Z{[3] \/ ([] .. [4]) : _2302{[1, 2]}}
There are 6 delayed goals.
Yes (0.00s cpu)

Finally, there are a number of n-ary constraints that apply to lists of sets: disjointness, union and intersection. For example:

---

all_disjoint(+Sets) Sets is a list of integers sets which are all disjoint all_union(+Sets, ?SetUnion) SetUnion is the union of all the sets in the list Sets all_intersection(+Sets, ?SetIntersection) SetIntersection is the intersection of all the sets in the list Sets

Figure 10.4: N-ary Set Relations

---

?- intsets(Sets, 5, 1, 5), all_intersection(Sets, Common).
Sets = [_2079{([] .. [1, 2, 3, 4, 5]) : _2055{0 .. 5}}, ... ]
Common = Common{([] .. [1, 2, 3, 4, 5]) : _3083{0 .. 5}}
There are 24 delayed goals.
Yes (0.00s cpu)

In most positions where a set or set variable is expected one can also use a set expression. A set expression is composed from ground sets (integer lists), set variables, and the following set operators:

Set1 /\ Set2       % intersection
Set1 \/ Set2       % union
Set1 \ Set2        % difference

When such set expressions occur, they are translated into auxiliary intersection/3, union/3 and difference/3 constraints, respectively.