NOPT042 Constraint programming: Tutorial 10 - Modeling with sets¶
Modelling with sets¶
In Picat, the cp solver doesn't work natively with sets and set constraints (unlike e.g. MiniZinc). Instead, we can model a set as an array (or a list) representing its characteristic vector. For a collection of sets, we can use a matrix or a list of lists.
- A subset $S\subseteq\{1,\dots,n\}$:
S = new_array(N), S :: 0..1 - Fixed cardinality subset:
exactly(K, S, 1) - Bounded cardinality subset:
at_most(K, S, 1),at_least(K, S, 1)(or we could usesum)
Set operations can be computed using bitwise logical constraints, e.g.
SintersectT = [S[I] #/\ T[I] : I in 1..N]
Alternatively, we could use a list of elements and require that the list is strictly increasing. In that case, we need to declare a list of length $N$ and have a decision variable for the length of the list. We can use 0 as a dummy value denoting that there are no more elements
S = new_list(N),
S :: 0..N,
SizeOfS :: 0..N,
increasing_strict(S[I] : I in 1..SizeOfS),
foreach(I in SizeOfS+1..N)
S[I] #= 0
end
A partition of $\{1,\dots,n\}$ with $k$ classes can be modelled as a function $\{1,\dots,n\}\to\{1,\dots,k\}$:
Partition = new_array(N),
Partition :: 1..K
Do not forget about symmetry breaking, e.g. Partition[1] #= 1 or
foreach(I in 1..K)
Partition[I] #<= I
end.
Similarly for a collection of $k$ pairwise disjoint subsets: using 0 to denote that an element is not covered by any subset.
Example: Finite projective plane¶
A projective plane geometry is a nonempty set X (whose elements are called "points"), along with a nonempty collection L of subsets of X (whose elements are called "lines"), such that:
- For every two distinct points, there is exactly one line that contains both points.
- The intersection of any two distinct lines contains exactly one point.
- There exists a set of four points, no three of which belong to the same line.
(from Wikipedia)
A projective plane of order N has $M=N^2+N+1$ points and the same number of lines, each line must have $K=N+1$ points and each point must lie on $K$ lines. A famous example is the Fano plane where $N=2$, $M=7$, and $K=3$.
If the order $N$ is a power of a prime power, it is easy to construct a projective plane of order $N$. It is conjectured otherwise, no projective plane exists. For $N=10$ this was famously proved by a computer-assisted proof (that finished in 1989). The case $N=12$ remains open.
Example: Ramsay's partition¶
Partition the integers 1 to $n$ into three parts, such that for no part are there three different numbers with two adding to the third. For which $n$ is it possible?
Example: Word Design for DNA Computing on Surfaces¶
Problem 033 from CSPLib: Find as large a set $S$ of strings (words) of length 8 over the alphabet $W = \{ A,C,G,T \}$ with the following properties:
- Each word in $S$ has 4 symbols from $\{ C,G \}$.
- Each pair of distinct words in $S$ differ in at least 4 positions.
- Each pair of words $x$ and $y$ in $S$ (where $x$ and $y$ may be identical) are such that $x^R$ and $y^C$ differ in at least 4 positions.
Here, $(x_1,\dots,x_8)^R = (x_8,\dots,x_1)$ is the reverse of $(x_1,\dots,x_8)$ and $(y_1,\dots,y_8)^C$ is the Watson-Crick complement of $(y_1,\dots,y_8)$, i.e., the word where each A is replaced by a T and vice versa and each C is replaced by a G and vice versa.