5.16. among

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

[BeldiceanuContejean94]

Constraint

πšŠπš–πš˜πš—πš(π™½πš…π™°πš,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚)

Synonym

πš‹πšŽπšπš πšŽπšŽπš—.

Arguments
π™½πš…π™°πšπšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°π™»πš„π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš)
Restrictions
π™½πš…π™°πšβ‰₯0
π™½πš…π™°πšβ‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
πšπš’πšœπšπš’πš—πšŒπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
Purpose

π™½πš…π™°πš is the number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ that take their value in πš…π™°π™»πš„π™΄πš‚.

Example
3,4,5,5,4,1,1,5,8

The πšŠπš–πš˜πš—πš 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}.

Typical
π™½πš…π™°πš>0
π™½πš…π™°πš<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
|πš…π™°π™»πš„π™΄πš‚|>1
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>|πš…π™°π™»πš„π™΄πš‚|
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

  • Items of πš…π™°π™»πš„π™΄πš‚ are permutable.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› that belongs to πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• (resp. does not belong to πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•) can be replaced by any other value in πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• (resp. not in πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•).

Remark

A similar constraint called πš‹πšŽπšπš πšŽπšŽπš— was introduced in CHIP in 1990.

The πšŒπš˜πš–πš–πš˜πš— constraint can be seen as a generalisation of the πšŠπš–πš˜πš—πš constraint where we allow the πšŸπšŠπš• attributes of the πš…π™°π™»πš„π™΄πš‚ collection to be domain variables.

A generalisation of this constraint when the values of πš…π™°π™»πš„π™΄πš‚ are not initially fixed is called πšŠπš–πš˜πš—πš_πšŸπšŠπš›.

When the variable π™½πš…π™°πš (i.e.,Β the first argument of the πšŠπš–πš˜πš—πš constraint) does not occur in any other constraints of the problem, it may be operationally more efficient to replace the πšŠπš–πš˜πš—πš constraint by an πšŠπš–πš˜πš—πš_πš•πš˜πš _πšžπš™ constraint where π™½πš…π™°πš is replaced by the corresponding interval [π™½πš…π™°πš Μ²,π™½πš…π™°πš Β―]. This stands for two reasons:

Algorithm

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

Systems

among in Choco, among in JaCoP.

See also

common keyword: πšŠπš›πš’πšπš‘, πšŠπšπš•πšŽπšŠπšœπš, πšŠπšπš–πš˜πšœπšΒ (value constraint), πšŒπš˜πšžπš—πšΒ (counting constraint), πšŒπš˜πšžπš—πšπšœΒ (value constraint,counting constraint), πšπš’πšœπšŒπš›πšŽπš™πšŠπš—πšŒπš’, πš–πšŠπš‘_πš—πšŸπšŠπš•πšžπšŽ, πš–πš’πš—_πš—πšŸπšŠπš•πšžπšŽ, πš—πšŸπšŠπš•πšžπšŽΒ (counting constraint).

generalisation: πšŠπš–πš˜πš—πš_πšŸπšŠπš›Β (πšŒπš˜πš—πšœπšπšŠπš—πš replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ).

implies: πšŠπš–πš˜πš—πš_πšŸπšŠπš›, πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πšŠπšπš–πš˜πšœπš.

related: πš›πš˜πš˜πšπšœΒ (can be used for expressing πšŠπš–πš˜πš—πš), πšœπš•πš’πšπš’πš—πš_πšŒπšŠπš›πš_πšœπš”πš’πš™0Β (counting constraint on maximal sequences).

shift of concept: πšŠπš–πš˜πš—πš_𝚜𝚎𝚚 (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πš’πš—πšπšŽπš›πšŸπšŠπš• and constraint applied in a sliding way), πšŒπš˜πš–πš–πš˜πš—.

soft variant: πš˜πš™πšŽπš—_πšŠπš–πš˜πš—πšΒ (open constraint).

specialisation: πšŠπš–πš˜πš—πš_πšπš’πšπš_0Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπšŸπšŠπš•πšžπšŽπšœ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ different from 0), πšŠπš–πš˜πš—πš_πš’πš—πšπšŽπš›πšŸπšŠπš•Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπšŸπšŠπš•πšžπšŽπšœ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπš’πš—πšπšŽπš›πšŸπšŠπš•), πšŠπš–πš˜πš—πš_πš•πš˜πš _πšžπš™Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πš’πš—πšπšŽπš›πšŸπšŠπš•), πšŠπš–πš˜πš—πš_πš–πš˜πšπšžπš•πš˜Β (list of πšŸπšŠπš•πšžπšŽπšœ replaced by list of πšŸπšŠπš•πšžπšŽπšœ 𝚟 such that 𝚟 mod πš€πš„π™Ύπšƒπ™Έπ™΄π™½πšƒ = πšπ™΄π™Όπ™°π™Έπ™½π™³π™΄πš), πšŽπš‘πšŠπšŒπšπš•πš’Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŒπš˜πš—πšœπšπšŠπš—πš and πšŸπšŠπš•πšžπšŽπšœ replaced by one single πšŸπšŠπš•πšžπšŽ).

system of constraints: πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (count the number of occurrences of different values).

used in graph description: πš’πš—.

uses in its reformulation: πšŒπš˜πšžπš—πš.

Keywords

characteristic of a constraint: automaton, automaton with counters, non-deterministic automaton.

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

constraint type: value constraint, counting constraint.

filtering: arc-consistency, SAT.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
π‘†πΈπΏπΉβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)

Arc arity
Arc constraint(s)
πš’πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›,πš…π™°π™»πš„π™΄πš‚)
Graph property(ies)
𝐍𝐀𝐑𝐂=π™½πš…π™°πš

Graph model

The arc constraint corresponds to the unary constraint πš’πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›,πš…π™°π™»πš„π™΄πš‚) defined in this catalogue. Since this is a unary constraint we employ the 𝑆𝐸𝐿𝐹 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 𝐍𝐀𝐑𝐂 graph property, the loops of the final graph are stressed in bold.

Figure 5.16.1. Initial and final graph of the πšŠπš–πš˜πš—πš constraint
ctrs/amongActrs/amongB
(a) (b)
Automaton

FigureΒ 5.16.2 depicts a first automaton that only accepts all the solutions of the πšŠπš–πš˜πš—πš constraint. This automaton uses a counter in order to record the number of satisfied constraints of the form πš…π™°πš i βˆˆπš…π™°π™»πš„π™΄πš‚ already encountered. To each variable πš…π™°πš i of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a 0-1 signature variable πš‚ i . The following signature constraint links πš…π™°πš i and πš‚ i : πš…π™°πš i βˆˆπš…π™°π™»πš„π™΄πš‚β‡”πš‚ i . The automaton counts the number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection that take their value in πš…π™°π™»πš„π™΄πš‚ and finally assigns this number to π™½πš…π™°πš.

Figure 5.16.2. Automaton (with a counter) of the πšŠπš–πš˜πš—πš constraint
ctrs/among1
Figure 5.16.3. Hypergraph of the reformulation corresponding to the automaton (with a counter) of the πšŠπš–πš˜πš—πš constraint: since all states variables are fixed to the unique state of the automaton, the transitions constraints share at most one variable and the constraint network is Berge-acyclic
ctrs/among2

We now describe a second counter free automaton that also only accepts all the solutions of the πšŠπš–πš˜πš—πš constraint. Without loss of generality, assume that the collection of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ contains at least one variable (i.e.,Β |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|β‰₯1). Let n and π’Ÿ respectively denote the number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, and the union of the domains of the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. Clearly, the maximum number of variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ that are assigned a value in πš…π™°π™»πš„π™΄πš‚ cannot exceed the quantity m=min(n,π™½πš…π™°πš Β―). The m+2 states of the automaton that only accepts all the solutions of the πšŠπš–πš˜πš—πš 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 (1≀i≀m). The intermediate states are indexed by the number of already encountered satisfied constraints of the form πš…π™°πš k βˆˆπš…π™°π™»πš„π™΄πš‚ 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, (jβˆˆπ’Ÿβˆ–πš…π™°π™»πš„π™΄πš‚), from every state s i , (i∈[0,m]), to itself.

  2. There is a transition, labeled by j, (jβˆˆπš…π™°π™»πš„π™΄πš‚), from every state s i , (i∈[0,m-1]), to the state s i+1 .

  3. There is a transition, labelled by i, from every state s i , (i∈[0,m]), to the final state s F .

This leads to an automaton that has mΒ·|π’Ÿ|+|π’Ÿβˆ–πš…π™°π™»πš„π™΄πš‚|+m+1 transitions. Since the maximum value of m is equal to n, in the worst case we have nΒ·|π’Ÿ|+|π’Ÿβˆ–πš…π™°π™»πš„π™΄πš‚|+n+1 transitions.

FigureΒ 5.16.4 depicts a counter free non deterministic automaton associated with the πšŠπš–πš˜πš—πš constraint under the hypothesis that (1)Β all variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are assigned a value in {0,1,2,3}, (2)Β |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| is equal to 3, (3)Β πš…π™°π™»πš„π™΄πš‚ corresponds to odd values. The sequence πš…π™°πš 1 ,πš…π™°πš 2 ,...,πš…π™°πš |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| ,π™½πš…π™°πš is passed to this automaton. A state s i (1≀i≀3) represents the fact that i odd values were already encountered, while s F represents the final state. A transition from s i (1≀i≀3) 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 π™½πš…π™°πš. 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 πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ and the potential value of the π™½πš…π™°πš. 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.

Figure 5.16.4. Counter free non deterministic automaton of the πšŠπš–πš˜πš—πš(π™½πš…π™°πš,βŒ©πš…π™°πš 1 ,πš…π™°πš 2 ,πš…π™°πš 3 βŒͺ,〈1,3βŒͺ) constraint assuming πš…π™°πš i ∈[0,3] (1≀i≀3), with initial state s 0 and final state s F
ctrs/among3
Figure 5.16.5. Counter free minimum-state deterministic automaton of the πšŠπš–πš˜πš—πš(π™½πš…π™°πš,βŒ©πš…π™°πš 1 ,πš…π™°πš 2 ,πš…π™°πš 3 βŒͺ,〈1,3βŒͺ) constraint assuming πš…π™°πš i ∈[0,3] (1≀i≀3), with initial state s 0 and final state s F
ctrs/among4

We make the following final observation. Since the Symmetries slot of the πšŠπš–πš˜πš—πš constraint indicates that the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ 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 π™½πš…π™°πš, πš…π™°πš 3 , πš…π™°πš 2 , πš…π™°πš 1 rather than the sequence πš…π™°πš 1 , πš…π™°πš 2 , πš…π™°πš 3 , π™½πš…π™°πš. This is achieved by respectively making s F and s 0 the initial and the final state, and by reversing each transition.