[ Reference Manual | Alphabetic Index ]

# library(fd_sets)

Solver over sets of integers (cooperates with lib(fd))   [more]

## Predicates

#(?Set, ?Card)
Card is the cardinality of the integer set Set
?Set :: ++Lwb..++Upb
Set is an integer set within the given bounds
all_disjoint(+Sets)
Sets is a list of integers sets which are all disjoint
all_intersection(+Sets, ?Intersection)
Intersection is the intersection of all the sets in the list Sets
all_union(+Sets, ?SetUnion)
SetUnion is the union of all the sets in the list Sets
difference(?Set1, ?Set2, ?Set3)
Set3 is the difference of the integer sets Set1 and Set2
?Set1 disjoint ?Set2
The integer sets Set1 and Set2 are disjoint
get_set_attribute(?Set, -Attr)
Get the set-attribute corresponding to Set
?X in ?Set
The integer X is member of the integer set Set
in(?X, ?Set, ?Bool)
Reified version of the set membership constraint
?Set in_set_range ++Lwb..++Upb
Set is an integer set within the given bounds
?Set1 includes ?Set2
Set1 includes (is a superset of) the integer set Set2
insetdomain(?Set, ?CardSel, ?ElemSel, ?Order)
Instantiate Set to a possible value
intersection(?Set1, ?Set2, ?Set3)
Set3 is the intersection of the integer sets Set1 and Set2
intset(?Set, +Min, +Max)
Set is a set containing numbers between Min and Max
intsets(?Sets, ?N, +Min, +Max)
Sets is a list of N sets containing numbers between Min and Max
is_exact_solver_var(?)
No description available
is_solver_type(?Term)
Succeeds if Term is a ground set or a set variable
is_solver_var(?Term)
Succeeds if Term is a set variable
membership_booleans(?Set, ?BoolArr)
BoolArr is an array of booleans describing Set
msg(?, ?, ?)
No description available
?X notin ?Set
The integer X is not a member of the integer set Set
potential_members(?Set, -List)
List is the list of elements of whose membership in Set is currently uncertain
?Set1 sameset ?Set2
The sets Set1 and Set2 are equal
set_range(?Set, -Lwb, -Upb)
Lwb and Upb are the current lower and upper bounds on Set
?Set1 subset ?Set2
Set1 is a (non-strict) subset of the integer set Set2
?Set1 subsetof ?Set2
Set1 is a (non-strict) subset of the integer set Set2
symdiff(?Set1, ?Set2, ?Set3)
Set3 is the symmetric difference of the integer sets Set1 and Set2
union(?Set1, ?Set2, ?Set3)
Set3 is the union of the integer sets Set1 and Set2
watch(?)
No description available
weight(?Set, ++ElementWeights, ?Weight)
According to the array of element weights, the weight of set Set is Weight

## Structures

struct int_sets(dom, off, lcard, ucard, added, removed, add, rem, card, booleans, value)
Attribute structure for set variables (and constants)

## Other Exports

export op(500, yfx, \)
export op(700, xfx, in_set_range)
export op(700, xfx, disjoint)
export op(700, xfx, sameset)
export op(700, xfx, in)
export op(700, xfx, notin)
export op(700, xfx, includes)
export op(700, xfx, subset)
export op(700, xfx, subsetof)

## Description

This is a solver for constraints over the domain of finite integer sets.

(Ground) integer sets are represented simply as sorted, duplicate-free lists of integers e.g.

```    	SetOfThree = [1,3,7]
EmptySet = []
```

### Set Variables

Set variables are variables which can eventually take a ground integer set as their value. They are characterized by a lower bound (the set of elements that are definitely in the set) and an upper bound (the set of elements that may be in the set). A set variable can be declared as follows:
```    	SetVar :: []..[1,2,3,4,5,6,7],
```
Since the lower bound is the empty set, this can be written as
```    	SetVar subset [1,2,3,4,5,6,7],
```
If the lower bound is the empty set and the upper bound is a set of consecutive integers, you can also write
```    	intset(SetVar, 1, 7)
```

### Set Constraints

Most of the usual set operations/relations are provided as constraints:
• membership
• non-membership
• inclusion (subset)
• equality
• intersection
• union
• difference
• symmetric difference
• disjointness
• cardinality
as well as a constraint on set weight. Note that there is no complement-constraint because the library has no concept of a set universe and cannot represent infinite sets.

On most argument positions where sets are expected, set expressions are allowed, e.g.

```    Set1 /\ Set2       % intersection
Set1 \/ Set2       % union
Set1 \ Set2        % difference
```
as well as references to array elements like Set[3].

### Search

The insetdomain/4 predicate can be used to enumerate all ground instantiations of a set variable, much like indomain/1 in the finite-domain case.

### Cooperation with a finite domain solver

This library comes in two flavours: lib(fd_sets) which cooperates with lib(fd), and lib(ic_sets) which cooperates with lib(ic). This is relevant only for those constraints which involve integer variables, e.g. the cardinality argument in #/2, the weight argument in weight/3 and the booleans in membership_booleans/2. These will be represented as fd- or ic-variables respectively.

## Examples

```% Example program: Steiner triplets
% Compute NB triplets of numbers from 1 to N such that
% any two triplets have at most one element in common.
% Try steiner(9,Sets).

:- lib(fd_sets).
:- lib(fd).

steiner(N, Sets) :-
NB is N * (N-1) // 6,		% compute number of triplets
intsets(Sets, NB, 1, N),	% initialise the set variables
( foreach(S,Sets) do
#(S,3)			% constrain their cardinality
),
( fromto(Sets,[S1|Ss],Ss,[]) do
( foreach(S2,Ss), param(S1) do
#(S1 /\ S2, C),		% constrain the cardinality
C #=< 1			% of pairwise intersections
)
),
label_sets(Sets).		% search

label_sets([]).
label_sets([S|Ss]) :-
insetdomain(S,_,_,_),
label_sets(Ss).
```