5.15. among

Origin

[BeldiceanuContejean94]

Constraint

among​(NVAR,​VARIABLES,​VALUES)​

Synonym(s)

between.

Argument(s)

NVAR	dvar
VARIABLES	collection​(var−dvar)​
VALUES	collection​(val−int)​

Restriction(s)

NVAR≥0

NVAR≤|VARIABLES|

required​(VARIABLES,​var)​

required​(VALUES,​val)​

distinct​(VALUES,​val)​

Purpose

NVAR is the number of variables of the collection VARIABLES that take their value in VALUES.

Example

( 3,​〈4,​5,​5,​4,​1〉,​ 〈1,​5,​8〉 )

The among constraint holds since exactly 3 values of the collection of variables 〈4,​5,​5,​4,​1〉 belong to the set of values ​{1,​5,​8}​.

Remark

A similar constraint called between was introduced in CHIP in 1990.

The common constraint can be seen as a generalisation of the among constraint where we allow the val attributes of the VALUES collection to be domain variables.

A generalisation of this constraint when the values of VALUES are not initially fixed is called among_var.

Algorithm

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

Systems

among in Jacop.

See also

among_var, among_diff_0, open_among, exactly, global_cardinality, count, common, nvalue, max_nvalue, min_nvalue.

Key words

characteristic of a constraint: automaton, automaton with counters.

constraint network structure: alpha-acyclic constraint network(2).

constraint type: value constraint, counting constraint.

filtering: arc-consistency, SAT.

Arc input(s)

VARIABLES

Arc generator

SELF↦collection​(variables)​

Arc arity

1

Arc constraint(s)

in​(variables.var,​VALUES)​

Graph property(ies)

NARC=NVAR

---

Graph model

The arc constraint corresponds to the unary constraint in​(variables.var,​VALUES)​ defined in this catalogue. Since this is a unary constraint we employ the SELF arc generator in order to produce an initial graph with a single loop on each vertex.

Parts (A) and (B) of Figure 5.15.1 respectively show the initial and final graph associated with the Example slot. Since we use the NARC graph property, the loops of the final graph are stressed in bold.

Figure 5.15.1. Initial and final graph of the among constraint

(a)	(b)

Automaton

Figure 5.15.2 depicts the automaton associated with the among constraint. To each variable VAR_i of the collection VARIABLES corresponds a 0-1 signature variable S_i. The following signature constraint links VAR_i and S_i: VAR_i∈VALUES⇔S_i. The automaton counts the number of variables of the VARIABLES collection that take their value in VALUES and finally assigns this number to NVAR.

Figure 5.15.2. Automaton of the among constraint

Figure 5.15.3. Hypergraph of the reformulation corresponding to the automaton of the among constraint