## 5.92. counts

Origin
Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi },\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ},\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }\right)$

Arguments
 $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$ $\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ}$ $\mathrm{\pi \pi \pi \pi }$ $\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }$ $\mathrm{\pi \pi \pi \pi }$
Restrictions
 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi },\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi },\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$
Purpose

Let $N$ be the number of variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection assigned to a value of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection. Enforce condition $N\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ}\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }$ to hold.

Example
$\left(β©1,3,4,9βͺ,β©4,5,5,4,1,5βͺ,=,3\right)$

Values 1, 3, 4 and 9 of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection are assigned to 3 items of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }=\beta ©4,5,5,4,1,5\beta ͺ$ collection. The $\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint holds since this number is in fact equal ($\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ}$ is set to $=$) to the last argument of the $\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint.

Typical
 $|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|>1$ $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>1$ $\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)>1$ $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|$ $\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ}\beta \left[=,<,\beta ₯,>,\beta €\right]$ $\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }>0$ $\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }<|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$
Symmetries
• Items of $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ are permutable.

• Items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are permutable.

• An occurrence of a value of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ that belongs to $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }.\mathrm{\pi \pi \pi }$ (resp. does not belong to $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }.\mathrm{\pi \pi \pi }$) can be replaced by any other value in $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }.\mathrm{\pi \pi \pi }$ (resp. not in $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }.\mathrm{\pi \pi \pi }$).

Arg. properties
• Contractible wrt. $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ when $\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ}\beta \left[<,\beta €\right]$.

• Extensible wrt. $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ when $\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ}\beta \left[\beta ₯,>\right]$.

• Aggregate: $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi }\right)$, $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\left(\mathrm{\pi \pi \pi \pi \pi }\right)$, $\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ}\left(\mathrm{\pi \pi }\right)$, $\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }\left(+\right)$ when $\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ}\beta \left[<,\beta €,\beta ₯,>\right]$.

Usage

Used in the Constraint(s) on sets slot for defining some constraints like $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$.

Reformulation

The $\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi },\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ},\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }\right)$ constraint can be expressed in term of the conjunction $\mathrm{\pi \pi \pi \pi \pi }$$\left(N,\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\right)\beta §N\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ}\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }$.

Systems

count in Gecode.

Used in

specialisation: $\mathrm{\pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\beta \mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$=$\mathrm{\pi  \pi °\pi »\pi \pi ΄}$).

Keywords
Arc input(s)

$\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$

Arc generator
$\mathrm{\pi \pi  \pi \pi ·\pi \pi Ά\pi }$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi },\mathrm{\pi \pi \pi \pi \pi \pi }\right)$

Arc arity
Arc constraint(s)
$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi }=\mathrm{\pi \pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi }$
Graph property(ies)
$\mathrm{\pi \pi \pi \pi }$$\mathrm{\pi \pi ΄\pi »\pi Ύ\pi Ώ}\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }$

Graph class
 $\beta ’$$\mathrm{\pi °\pi ²\pi \pi ²\pi »\pi Έ\pi ²}$ $\beta ’$$\mathrm{\pi ±\pi Έ\pi Ώ\pi °\pi \pi \pi Έ\pi \pi ΄}$ $\beta ’$$\mathrm{\pi ½\pi Ύ}_\mathrm{\pi »\pi Ύ\pi Ύ\pi Ώ}$

Graph model

Because of the arc constraint $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi }=\mathrm{\pi \pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi }$ and since each domain variable can take at most one value, $\mathrm{\pi \pi \pi \pi }$ is the number of variables taking a value in the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection.

PartsΒ (A) andΒ (B) of FigureΒ 5.92.1 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{\pi \pi \pi \pi }$ graph property, the arcs of the final graph are stressed in bold.

Automaton

FigureΒ 5.92.2 depicts the automaton associated with the $\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint. To each variable ${\mathrm{\pi  \pi °\pi }}_{i}$ of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ corresponds a 0-1 signature variable ${S}_{i}$. The following signature constraint links ${\mathrm{\pi  \pi °\pi }}_{i}$ and ${S}_{i}$: ${\mathrm{\pi  \pi °\pi }}_{i}\beta \mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\beta {S}_{i}$.