## 5.16. among

Origin
Constraint

$\mathrm{\pi \pi \pi \pi \pi }\left(\mathrm{\pi ½\pi  \pi °\pi },\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\right)$

Synonym

.

Arguments
 $\mathrm{\pi ½\pi  \pi °\pi }$ $\mathrm{\pi \pi \pi \pi }$ $\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 ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi }\right)$
Restrictions
 $\mathrm{\pi ½\pi  \pi °\pi }\beta ₯0$ $\mathrm{\pi ½\pi  \pi °\pi }\beta €|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$ $\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)$ $\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)$
Purpose

$\mathrm{\pi ½\pi  \pi °\pi }$ is the number of variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ that take their value in $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$.

Example
$\left(\begin{array}{c}3,β©4,5,5,4,1βͺ,\hfill \\ β©1,5,8βͺ\hfill \end{array}\right)$

The $\mathrm{\pi \pi \pi \pi \pi }$ constraint holds since exactly 3 values of the collection of variables $\beta ©4,5,5,4,1\beta ͺ$ belong to the set of values $\left\{1,5,8\right\}$.

Typical
 $\mathrm{\pi ½\pi  \pi °\pi }>0$ $\mathrm{\pi ½\pi  \pi °\pi }<|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$ $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>1$ $|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|>1$ $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|$
Symmetries
• Items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are permutable.

• Items of $\mathrm{\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 }$).

Remark

A similar constraint called was introduced in CHIP in 1990.

The $\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint can be seen as a generalisation of the $\mathrm{\pi \pi \pi \pi \pi }$ constraint where we allow the $\mathrm{\pi \pi \pi }$ attributes of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection to be domain variables.

A generalisation of this constraint when the values of $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ are not initially fixed is called $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$.

When the variable $\mathrm{\pi ½\pi  \pi °\pi }$ (i.e.,Β the first argument of the $\mathrm{\pi \pi \pi \pi \pi }$ constraint) does not occur in any other constraints of the problem, it may be operationally more efficient to replace the $\mathrm{\pi \pi \pi \pi \pi }$ constraint by an constraint where $\mathrm{\pi ½\pi  \pi °\pi }$ is replaced by the corresponding interval $\left[\underset{Μ²}{\mathrm{\pi ½\pi  \pi °\pi }},\stackrel{Β―}{\mathrm{\pi ½\pi  \pi °\pi }}\right]$. This stands for two reasons:

• First, by using an constraint rather than an $\mathrm{\pi \pi \pi \pi \pi }$ constraint, we avoid the filtering algorithm related to $\mathrm{\pi ½\pi  \pi °\pi }$.

• Second, unlike the $\mathrm{\pi \pi \pi \pi \pi }$ constraint where we need to fix all its variables to get entailment, the constraint can be entailed before all its variables get fixed. As a result, this potentially avoid unnecessary calls to its filtering algorithm.

Algorithm

A filtering algorithm achieving arc -consistency was given by BessiΓ¨re et al. inΒ [BessiereHebrardHnichKiziltanWalsh05ERCIM], [BessiereHebrardHnichKiziltanWalsh06ERCIM].

Systems

among in Choco, among in JaCoP.

generalisation: $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$).

shift of concept: $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ and constraint applied in a sliding way), $\mathrm{\pi \pi \pi \pi \pi \pi }$.

specialisation: $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }_\mathtt{0}$Β ($\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 }$ different from 0), $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \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 }\beta \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$), Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$), $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$Β (list of $\mathrm{\pi \pi \pi \pi \pi \pi }$ replaced by list of $\mathrm{\pi \pi \pi \pi \pi \pi }$ $\mathrm{\pi }$ such that $\mathrm{\pi }\mathrm{mod}\mathrm{\pi \pi \pi Ύ\pi \pi Έ\pi ΄\pi ½\pi }$ = $\mathrm{\pi \pi ΄\pi Ό\pi °\pi Έ\pi ½\pi ³\pi ΄\pi }$), $\mathrm{\pi \pi ‘\pi \pi \pi \pi \pi ’}$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ and $\mathrm{\pi \pi \pi \pi \pi \pi }$ replaced by one single $\mathrm{\pi \pi \pi \pi \pi }$).

system of constraints: $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi ’}$Β (count the number of occurrences of different values).

Keywords
Arc input(s)

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

Arc generator
$\mathrm{\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 }\right)$

Arc arity
Arc constraint(s)
$\mathrm{\pi \pi }$$\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi },\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\right)$
Graph property(ies)
$\mathrm{\pi \pi \pi \pi }$$=\mathrm{\pi ½\pi  \pi °\pi }$

Graph model

The arc constraint corresponds to the unary constraint $\mathrm{\pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi },\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\right)$ defined in this catalogue. Since this is a unary constraint we employ the $\mathrm{\pi \pi Έ\pi Ώ\pi Ή}$ arc generator in order to produce an initial graph with a single loop on each vertex.

PartsΒ (A) andΒ (B) of FigureΒ 5.16.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 loops of the final graph are stressed in bold.

Automaton

FigureΒ 5.16.2 depicts a first automaton that only accepts all the solutions of the $\mathrm{\pi \pi \pi \pi \pi }$ constraint. This automaton uses a counter in order to record the number of satisfied constraints of the form ${\mathrm{\pi  \pi °\pi }}_{i}\beta \mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ already encountered. 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 ${\mathrm{\pi }}_{i}$. The following signature constraint links ${\mathrm{\pi  \pi °\pi }}_{i}$ and ${\mathrm{\pi }}_{i}$: ${\mathrm{\pi  \pi °\pi }}_{i}\beta \mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\beta {\mathrm{\pi }}_{i}$. The automaton counts the number of variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection that take their value in $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ and finally assigns this number to $\mathrm{\pi ½\pi  \pi °\pi }$.

We now describe a second counter free automaton that also only accepts all the solutions of the $\mathrm{\pi \pi \pi \pi \pi }$ constraint. Without loss of generality, assume that the collection of variables $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ contains at least one variable (i.e.,Β $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|\beta ₯1$). Let $n$ and $\mathrm{\pi }$ respectively denote the number of variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$, and the union of the domains of the variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$. Clearly, the maximum number of variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ that are assigned a value in $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ cannot exceed the quantity $m=min\left(n,\stackrel{Β―}{\mathrm{\pi ½\pi  \pi °\pi }}\right)$. The $m+2$ states of the automaton that only accepts all the solutions of the $\mathrm{\pi \pi \pi \pi \pi }$ constraint can be defined in the following way:

• We have an initial state labelled by ${s}_{0}$.

• We have $m$ intermediate states labelled by ${s}_{i}$ $\left(1\beta €i\beta €m\right)$. The intermediate states are indexed by the number of already encountered satisfied constraints of the form ${\mathrm{\pi  \pi °\pi }}_{k}\beta \mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ from the initial state ${s}_{0}$ to the state ${s}_{i}$.

• We have a final state labelled by ${s}_{F}$.

Three classes of transitions are respectively defined in the following way:

1. There is a transition, labeled by $j$, $\left(j\beta \mathrm{\pi }\beta \mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\right)$, from every state ${s}_{i}$, $\left(i\beta \left[0,m\right]\right)$, to itself.

2. There is a transition, labeled by $j$, $\left(j\beta \mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\right)$, from every state ${s}_{i}$, $\left(i\beta \left[0,m-1\right]\right)$, to the state ${s}_{i+1}$.

3. There is a transition, labelled by $i$, from every state ${s}_{i}$, $\left(i\beta \left[0,m\right]\right)$, to the final state ${s}_{F}$.

This leads to an automaton that has $mΒ·|\mathrm{\pi }|+|\mathrm{\pi }\beta \mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|+m+1$ transitions. Since the maximum value of $m$ is equal to $n$, in the worst case we have $nΒ·|\mathrm{\pi }|+|\mathrm{\pi }\beta \mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|+n+1$ transitions.

FigureΒ 5.16.4 depicts a counter free non deterministic automaton associated with the $\mathrm{\pi \pi \pi \pi \pi }$ constraint under the hypothesis that (1)Β all variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are assigned a value in $\left\{0,1,2,3\right\}$, (2)Β $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$ is equal to 3, (3)Β $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ corresponds to odd values. The sequence ${\mathrm{\pi  \pi °\pi }}_{1},{\mathrm{\pi  \pi °\pi }}_{2},...,{\mathrm{\pi  \pi °\pi }}_{|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|},\mathrm{\pi ½\pi  \pi °\pi }$ is passed to this automaton. A state ${s}_{i}$ $\left(1\beta €i\beta €3\right)$ represents the fact that $i$ odd values were already encountered, while ${s}_{F}$ represents the final state. A transition from ${s}_{i}$ $\left(1\beta €i\beta €3\right)$ to ${s}_{F}$ is labelled by $i$ and represents the fact that we can only go in the final state from a state that is compatible with the total number of odd values enforced by $\mathrm{\pi ½\pi  \pi °\pi }$. Note that non determinism only occurs if there is a non -empty intersection between the set of potential values that can be assigned to the variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ and the potential value of the $\mathrm{\pi ½\pi  \pi °\pi }$. While the counter free non deterministic automaton depicted by FigureΒ 5.16.4 has 5 states and 18 transitions, its minimum -state deterministic counterpart shown in FigureΒ 5.16.5 has 7 states and 23 transitions.

We make the following final observation. Since the Symmetries slot of the $\mathrm{\pi \pi \pi \pi \pi }$ constraint indicates that the variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are permutable, and since all incoming transitions to any state of the automaton depicted by FigureΒ 5.16.4 are labelled with distinct values, we can mechanically construct from this automaton a counter free deterministic automaton that takes as input the sequence $\mathrm{\pi ½\pi  \pi °\pi }$, ${\mathrm{\pi  \pi °\pi }}_{3}$, ${\mathrm{\pi  \pi °\pi }}_{2}$, ${\mathrm{\pi  \pi °\pi }}_{1}$ rather than the sequence ${\mathrm{\pi  \pi °\pi }}_{1}$, ${\mathrm{\pi  \pi °\pi }}_{2}$, ${\mathrm{\pi  \pi °\pi }}_{3}$, $\mathrm{\pi ½\pi  \pi °\pi }$. This is achieved by respectively making ${s}_{F}$ and ${s}_{0}$ the initial and the final state, and by reversing each transition.