Global Constraint Catalog: Ccount

5.91. count

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

[Sicstus95]

Constraint

$𝚌𝚘𝚞𝚗𝚝 (𝚅𝙰𝙻𝚄𝙴, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚁𝙴𝙻𝙾𝙿, 𝙻𝙸𝙼𝙸𝚃)$

Synonyms

$𝚘𝚌𝚌𝚞𝚛𝚎𝚗𝚌𝚎𝚖𝚊𝚡$ , $𝚘𝚌𝚌𝚞𝚛𝚎𝚗𝚌𝚎𝚖𝚒𝚗$ , $𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎$ .

Arguments

$𝚅𝙰𝙻𝚄𝙴$	$𝚒𝚗𝚝$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚁𝙴𝙻𝙾𝙿$	$𝚊𝚝𝚘𝚖$
$𝙻𝙸𝙼𝙸𝚃$	$𝚍𝚟𝚊𝚛$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

𝚁𝙴𝙻𝙾𝙿 \in [=, \neq, <, \geq, >, \leq]

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〉, \geq, 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 $\geq$ ) $𝙻𝙸𝙼𝙸𝚃 = 2$ .

Typical

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) > 1

𝚁𝙴𝙻𝙾𝙿 \in [=, <, \geq, >, \leq]

𝙻𝙸𝙼𝙸𝚃 > 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 $𝚅𝙰𝙻𝚄𝙴$ .

Arg. properties

Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚁𝙴𝙻𝙾𝙿 \in [<, \leq]$ .
Extensible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚁𝙴𝙻𝙾𝙿 \in [\geq, >]$ .
Aggregate: $𝚅𝙰𝙻𝚄𝙴 (𝚒𝚍)$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 (𝚞𝚗𝚒𝚘𝚗)$ , $𝚁𝙴𝙻𝙾𝙿 (𝚒𝚍)$ , $𝙻𝙸𝙼𝙸𝚃 (+)$ when $𝚁𝙴𝙻𝙾𝙿 \in [<, \leq, \geq, >]$ .

Remark

Similar to the $𝚊𝚖𝚘𝚗𝚐$ constraint. Both, in JaCoP (http://www.jacop.eu/) and in MiniZinc (http://www.minizinc.org/) $𝚁𝙴𝙻𝙾𝙿$ is implicitly set to $=$ .

Reformulation

The $𝚌𝚘𝚞𝚗𝚝$ $(𝚅𝙰𝙻𝚄𝙴, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚁𝙴𝙻𝙾𝙿, 𝙻𝙸𝙼𝙸𝚃)$ constraint can be expressed in term of the conjunction $𝚊𝚖𝚘𝚗𝚐$ $(N, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 〈 𝚅𝙰𝙻𝚄𝙴 〉) \land N 𝚁𝙴𝙻𝙾𝙿 𝙻𝙸𝙼𝙸𝚃$ .

Systems

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

See also

assignment dimension added: $𝚊𝚜𝚜𝚒𝚐𝚗_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝𝚜$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ = $𝚅𝙰𝙻𝚄𝙴$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \in 𝚅𝙰𝙻𝚄𝙴𝚂$ and assignment dimension introduced).

common keyword: $𝚊𝚖𝚘𝚗𝚐$ (value constraint,counting constraint), $𝚊𝚛𝚒𝚝𝚑$ (value constraint), $𝚌𝚘𝚖𝚙𝚊𝚛𝚎_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝$ (counting constraint), $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ , $𝚖𝚊𝚡_𝚗𝚟𝚊𝚕𝚞𝚎$ , $𝚖𝚒𝚗_𝚗𝚟𝚊𝚕𝚞𝚎$ (value constraint,counting constraint), $𝚗𝚟𝚊𝚕𝚞𝚎$ (counting constraint).

generalisation: $𝚌𝚘𝚞𝚗𝚝𝚜$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ = $𝚅𝙰𝙻𝚄𝙴$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \in 𝚅𝙰𝙻𝚄𝙴𝚂$ ).

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

𝑆𝐸𝐿𝐹

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜)

Arc arity

Arc constraint(s)

𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛 = 𝚅𝙰𝙻𝚄𝙴

Graph property(ies)

𝐍𝐀𝐑𝐂

𝚁𝙴𝙻𝙾𝙿 𝙻𝙸𝙼𝙸𝚃

Graph model

Parts (A) and (B) of Figure 5.91.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.91.1. Initial and final graph of the $𝚌𝚘𝚞𝚗𝚝$ constraint


(a)	(b)

Automaton: Figure 5.91.2 depicts the automaton associated with the $𝚌𝚘𝚞𝚗𝚝$ constraint. To each variable ${𝚅𝙰𝚁}_{i}$ of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a 0-1 signature variable $S_{i}$ . The following signature constraint links ${𝚅𝙰𝚁}_{i}$ and $S_{i}$ : ${𝚅𝙰𝚁}_{i} = 𝚅𝙰𝙻𝚄𝙴 \Leftrightarrow S_{i}$ .

Figure 5.91.2. Automaton of the $𝚌𝚘𝚞𝚗𝚝$ constraint

Figure 5.91.3. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the $𝚌𝚘𝚞𝚗𝚝$ constraint: since all states variables $Q_{0}, Q_{1}, \dots, Q_{n}$ are fixed to the unique state $s$ of the automaton, the transitions constraints share only the counter variable $C$ and the constraint network is Berge-acyclic

Global Constraint Catalog

5. Global Constraint Catalogue

5.91. count

Figure 5.91.1. Initial and final graph of the $𝚌𝚘𝚞𝚗𝚝$ constraint

Figure 5.91.2. Automaton of the $𝚌𝚘𝚞𝚗𝚝$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.91. count

Figure 5.91.1. Initial and final graph of the 𝚌𝚘𝚞𝚗𝚝 constraint

Figure 5.91.2. Automaton of the 𝚌𝚘𝚞𝚗𝚝 constraint

Figure 5.91.1. Initial and final graph of the $𝚌𝚘𝚞𝚗𝚝$ constraint

Figure 5.91.2. Automaton of the $𝚌𝚘𝚞𝚗𝚝$ constraint