[ The ECLiPSe Libraries | Reference Manual | Alphabetic Index ]

# library(fd_sets)

Solver over sets of integers (cooperates with lib(fd))

## 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
compare_instances_set(?, ?, ?)
No description available
copy_term_set(?, ?)
No description available
delayed_goals_number_set(?, ?)
No description available
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
?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_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
?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
print_setvar(?, ?)
No description available
?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
suspensions_set(?, ?, ?)
No description available
symdiff(?Set1, ?Set2, ?Set3)
Set3 is the symmetric difference of the integer sets Set1 and Set2
test_unify_sets(?, ?)
No description available
unify_sets(?, ?, ?)
No description available
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, 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)

## 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
```

### 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).
```