Global Constraint Catalog: Cnclass

5.271. nclass

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚗𝚟𝚊𝚕𝚞𝚎$ .

Constraint

$𝚗𝚌𝚕𝚊𝚜𝚜 (𝙽𝙲𝙻𝙰𝚂𝚂, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂)$

Type

𝚅𝙰𝙻𝚄𝙴𝚂

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚕 - 𝚒𝚗𝚝)

Arguments

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

Restrictions

| 𝚅𝙰𝙻𝚄𝙴𝚂 | \geq 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

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

𝙽𝙲𝙻𝙰𝚂𝚂 \geq 0

𝙽𝙲𝙻𝙰𝚂𝚂 \leq 𝚖𝚒𝚗 (| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |, | 𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 |)

𝙽𝙲𝙻𝙰𝚂𝚂 \leq

𝚛𝚊𝚗𝚐𝚎

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂, 𝚙)

| 𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 | \geq 2

Purpose

Number of partitions of the collection $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ such that at least one value is assigned to at least one variable of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Example

(2, 〈3, 2, 7, 2, 6〉, 〈𝚙 - 〈1, 3〉, 𝚙 - 〈4〉, 𝚙 - 〈2, 6〉〉)

Note that the values of $〈 3, 2, 7, 2, 6 〉$ occur within partitions $𝚙 - 〈 1, 3 〉$ and $𝚙 - 〈 2, 6 〉$ but not within $𝚙 - 〈 4 〉$ . Consequently, the $𝚗𝚌𝚕𝚊𝚜𝚜$ constraint holds since its first argument $𝙽𝙲𝙻𝙰𝚂𝚂$ is set to value 2.

Typical

𝙽𝙲𝙻𝙰𝚂𝚂 > 1

𝙽𝙲𝙻𝙰𝚂𝚂 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝙽𝙲𝙻𝙰𝚂𝚂 <

𝚛𝚊𝚗𝚐𝚎

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

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > | 𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 |

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.
Items of $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ are permutable.
Items of $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 . 𝚙$ are permutable.
An occurrence of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ can be replaced by any other value that also belongs to the same partition of $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ .
All occurrences of two distinct tuples of values in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ or $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 . 𝚙 . 𝚟𝚊𝚕$ can be swapped; all occurrences of a tuple of values in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ or $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 . 𝚙 . 𝚟𝚊𝚕$ can be renamed to any unused tuple of values.

Arg. properties

Functional dependency: $𝙽𝙲𝙻𝙰𝚂𝚂$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ .
Extensible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙽𝙲𝙻𝙰𝚂𝚂 = | 𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 |$ .

Algorithm

[Beldiceanu01], [BeldiceanuCarlssonThiel02].

See also

related: $𝚗𝚎𝚚𝚞𝚒𝚟𝚊𝚕𝚎𝚗𝚌𝚎$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \in 𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \mod 𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝$ ), $𝚗𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \in 𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 / 𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝$ ), $𝚗𝚙𝚊𝚒𝚛$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \in 𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ replaced by $𝚙𝚊𝚒𝚛$ of $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜$ ).

specialisation: $𝚗𝚟𝚊𝚕𝚞𝚎$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \in 𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ ).

used in graph description: $𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ .

Keywords

characteristic of a constraint: partition.

constraint arguments: pure functional dependency.

constraint type: counting constraint, value partitioning constraint.

final graph structure: strongly connected component, equivalence.

modelling: number of distinct equivalence classes, functional dependency.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝐶𝐿𝐼𝑄𝑈𝐸

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

Arc arity

Arc constraint(s)

𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗

(𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛, 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛, 𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂)

Graph property(ies)

𝐍𝐒𝐂𝐂

= 𝙽𝙲𝙻𝙰𝚂𝚂

Graph model

Parts (A) and (B) of Figure 5.271.1 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐒𝐂𝐂$ graph property we show the different strongly connected components of the final graph. Each strongly connected component corresponds to a class of values that was assigned to some variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection. We effectively use two classes of values that respectively correspond to values ${3}$ and ${2, 6}$ . Note that we do not consider value 7 since it does not belong to the different classes of values we gave: all corresponding arc constraints do not hold.

Figure 5.271.1. Initial and final graph of the $𝚗𝚌𝚕𝚊𝚜𝚜$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.271. nclass

Figure 5.271.1. Initial and final graph of the 𝚗𝚌𝚕𝚊𝚜𝚜 constraint

Figure 5.271.1. Initial and final graph of the $𝚗𝚌𝚕𝚊𝚜𝚜$ constraint