Global Constraint Catalog: Ccounts

5.92. counts

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Derived from $𝚌𝚘𝚞𝚗𝚝$ .

Constraint

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

Arguments

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

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝙻𝚄𝙴𝚂, 𝚟𝚊𝚕)

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝚅𝙰𝙻𝚄𝙴𝚂, 𝚟𝚊𝚕)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

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

Purpose

Let $N$ be the number of variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection assigned to a value of the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection. Enforce condition $N 𝚁𝙴𝙻𝙾𝙿 𝙻𝙸𝙼𝙸𝚃$ to hold.

Example

(〈1, 3, 4, 9〉, 〈4, 5, 5, 4, 1, 5〉, =, 3)

Values 1, 3, 4 and 9 of the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection are assigned to 3 items of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 = 〈 4, 5, 5, 4, 1, 5 〉$ collection. The $𝚌𝚘𝚞𝚗𝚝𝚜$ constraint holds since this number is in fact equal ( $𝚁𝙴𝙻𝙾𝙿$ is set to $=$ ) to the last argument of the $𝚌𝚘𝚞𝚗𝚝𝚜$ constraint.

Typical

| 𝚅𝙰𝙻𝚄𝙴𝚂 | > 1

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

𝚛𝚊𝚗𝚐𝚎

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

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

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

𝙻𝙸𝙼𝙸𝚃 > 0

𝙻𝙸𝙼𝙸𝚃 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

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 $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ ).

Arg. properties

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

Usage

Used in the Constraint(s) on sets slot for defining some constraints like $𝚊𝚜𝚜𝚒𝚐𝚗_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝𝚜$ .

Reformulation

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

Systems

count in Gecode.

Used in

$𝚊𝚜𝚜𝚒𝚐𝚗_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝𝚜$ .

common keyword: $𝚊𝚖𝚘𝚗𝚐$ (value constraint,counting constraint).

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

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.

final graph structure: acyclic, bipartite, no loop.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ $𝚅𝙰𝙻𝚄𝙴𝚂$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛 = 𝚟𝚊𝚕𝚞𝚎𝚜 . 𝚟𝚊𝚕

Graph property(ies)

𝐍𝐀𝐑𝐂

𝚁𝙴𝙻𝙾𝙿 𝙻𝙸𝙼𝙸𝚃

Graph class

•

𝙰𝙲𝚈𝙲𝙻𝙸𝙲

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

Because of the arc constraint $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛 = 𝚟𝚊𝚕𝚞𝚎𝚜 . 𝚟𝚊𝚕$ and since each domain variable can take at most one value, $𝐍𝐀𝐑𝐂$ is the number of variables taking a value in the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection.

Parts (A) and (B) of Figure 5.92.1 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐀𝐑𝐂$ graph property, the arcs of the final graph are stressed in bold.

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


(a)	(b)

Automaton: Figure 5.92.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} \in 𝚅𝙰𝙻𝚄𝙴𝚂 \Leftrightarrow S_{i}$ .

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

Figure 5.92.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.92. counts

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

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

Global Constraint Catalog

5. Global Constraint Catalogue

5.92. counts

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

Figure 5.92.2. Automaton of the 𝚌𝚘𝚞𝚗𝚝𝚜 constraint

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

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