5.77. count

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

[Sicstus95]

Constraint

πšŒπš˜πšžπš—πš(πš…π™°π™»πš„π™΄,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšπ™΄π™»π™Ύπ™Ώ,π™»π™Έπ™Όπ™Έπšƒ)

Synonyms

πš˜πšŒπšŒπšžπš›πšŽπš—πšŒπšŽπš–πšŠπš‘, πš˜πšŒπšŒπšžπš›πšŽπš—πšŒπšŽπš–πš’πš—, πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ.

Arguments
πš…π™°π™»πš„π™΄πš’πš—πš
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πšπ™΄π™»π™Ύπ™ΏπšŠπšπš˜πš–
π™»π™Έπ™Όπ™ΈπšƒπšπšŸπšŠπš›
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πšπ™΄π™»π™Ύπ™Ώβˆˆ[=,β‰ ,<,β‰₯,>,≀]
Purpose

Let N be the number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection assigned to value πš…π™°π™»πš„π™΄; Enforce condition N πšπ™΄π™»π™Ύπ™Ώ π™»π™Έπ™Όπ™Έπšƒ to hold.

Example
5,4,5,5,4,5,β‰₯,2

The πšŒπš˜πšžπš—πš constraint holds since value πš…π™°π™»πš„π™΄=5 occurs 3 times within the items of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚=〈4,5,5,4,5βŒͺ, which is greater than or equal to (πšπ™΄π™»π™Ύπ™Ώ is set to β‰₯) π™»π™Έπ™Όπ™Έπšƒ=2.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
π™»π™Έπ™Όπ™Έπšƒ>0
π™»π™Έπ™Όπ™Έπšƒ<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› that is different from πš…π™°π™»πš„π™΄ can be replaced by any other value that is also different from πš…π™°π™»πš„π™΄.

Remark

Similar to the πšŠπš–πš˜πš—πš constraint.

In JaCoP (http://www.jacop.eu/) πšπ™΄π™»π™Ύπ™Ώ is implicitly set to =.

Reformulation

The πšŒπš˜πšžπš—πš(πš…π™°π™»πš„π™΄,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, πšπ™΄π™»π™Ύπ™Ώ ,π™»π™Έπ™Όπ™Έπšƒ) constraint can be expressed in term of the conjunction πšŠπš–πš˜πš—πš(N,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,βŒ©πš…π™°π™»πš„π™΄βŒͺ) ∧ N πšπ™΄π™»π™Ύπ™Ώ π™»π™Έπ™Όπ™Έπšƒ.

Systems

occurence in Choco, count in Gecode, count in JaCoP, count in SICStus.

See also

assignment dimension added: πšŠπšœπšœπš’πšπš—_πšŠπš—πš_πšŒπš˜πšžπš—πšπšœΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ=πš…π™°π™»πš„π™΄ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπš…π™°π™»πš„π™΄πš‚ and assignment dimension introduced).

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

generalisation: πšŒπš˜πšžπš—πšπšœΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ=πš…π™°π™»πš„π™΄ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπš…π™°π™»πš„π™΄πš‚).

related: πš›πš˜πš˜πšπšœ.

used in reformulation: πšŠπš–πš˜πš—πš.

Keywords

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.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πš…π™°π™»πš„π™΄
Graph property(ies)
𝐍𝐀𝐑𝐂 πšπ™΄π™»π™Ύπ™Ώ π™»π™Έπ™Όπ™Έπšƒ

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.77.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.77.1. Initial and final graph of the πšŒπš˜πšžπš—πš constraint
ctrs/countActrs/countB
(a) (b)
Automaton

FigureΒ 5.77.2 depicts the automaton associated with the πšŒπš˜πšžπš—πš constraint. To each variable πš…π™°πš i of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a 0-1 signature variable πš‚ i . The following signature constraint links πš…π™°πš i and πš‚ i : πš…π™°πš i =πš…π™°π™»πš„π™΄β‡”πš‚ i .

Figure 5.77.2. Automaton of the πšŒπš˜πšžπš—πš constraint
ctrs/count1
Figure 5.77.3. Hypergraph of the reformulation corresponding to the automaton of the πšŒπš˜πšžπš—πš constraint
ctrs/count2