Global Constraint Catalog: Csame

5.337. same_intersection

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚜𝚊𝚖𝚎$ and $𝚌𝚘𝚖𝚖𝚘𝚗$ .

Constraint

$𝚜𝚊𝚖𝚎_𝚒𝚗𝚝𝚎𝚛𝚜𝚎𝚌𝚝𝚒𝚘𝚗 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2)$

Arguments

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

Each value, which occurs both in the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and in the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ collections, has the same number of occurrences in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ as well as in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ .

Example

(〈1, 9, 1, 5, 2, 1〉, 〈9, 1, 1, 1, 3, 5, 8〉)

First note that the values, which occur both in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 = 〈 1, 9, 1, 5, 2, 1 〉$ as well as in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 = 〈 9, 1, 1, 1, 3, 5, 8 〉$ correspond to values 1, 5, and 9. Consequently, the $𝚜𝚊𝚖𝚎_𝚒𝚗𝚝𝚎𝚛𝚜𝚎𝚌𝚝𝚒𝚘𝚗$ constraint holds since these values 1, 5, and 9 have the same number of occurrences in both collections (i.e., they respectively occur 3, 1, and 1 times within $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ ).

Typical

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

𝚛𝚊𝚗𝚐𝚎

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

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

𝚛𝚊𝚗𝚐𝚎

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

Symmetries

Arguments are permutable w.r.t. permutation $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2)$ .
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ are permutable.
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ are permutable.
All occurrences of two distinct values in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛$ or $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛$ can be swapped; all occurrences of a value in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛$ or $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛$ can be renamed to any unused value.

implied by: $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚘𝚗_𝚒𝚗𝚝𝚎𝚛𝚜𝚎𝚌𝚝𝚒𝚘𝚗$ , $𝚜𝚊𝚖𝚎$ .

Keywords

constraint arguments: constraint between two collections of variables.

constraint type: constraint on the intersection.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 = 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛

Graph property(ies)

for all connected components:

𝐍𝐒𝐎𝐔𝐑𝐂𝐄

=

𝐍𝐒𝐈𝐍𝐊

Graph model

Parts (A) and (B) of Figure 5.337.1 respectively show the initial and final graph associated with the Example slot. The $𝚜𝚊𝚖𝚎_𝚒𝚗𝚝𝚎𝚛𝚜𝚎𝚌𝚝𝚒𝚘𝚗$ constraint holds since each connected component of the final graph has the same number of sources and sinks. Note that all the vertices corresponding to the variables that take values 2, 3 or 8 were removed from the final graph since there is no arc for which the associated equality constraint holds.

Figure 5.337.1. Initial and final graph of the $𝚜𝚊𝚖𝚎_𝚒𝚗𝚝𝚎𝚛𝚜𝚎𝚌𝚝𝚒𝚘𝚗$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.337. same_intersection

Figure 5.337.1. Initial and final graph of the 𝚜𝚊𝚖𝚎_𝚒𝚗𝚝𝚎𝚛𝚜𝚎𝚌𝚝𝚒𝚘𝚗 constraint

Figure 5.337.1. Initial and final graph of the $𝚜𝚊𝚖𝚎_𝚒𝚗𝚝𝚎𝚛𝚜𝚎𝚌𝚝𝚒𝚘𝚗$ constraint