Global Constraint Catalog: Clength_first

5.186. length_first_sequence

DESCRIPTION

LINKS

AUTOMATON

Origin

Inspired by $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$

Constraint

$𝚕𝚎𝚗𝚐𝚝𝚑_𝚏𝚒𝚛𝚜𝚝_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎 (𝙻𝙴𝙽, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Arguments

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

Restrictions

𝙻𝙴𝙽 \geq 0

𝙻𝙴𝙽 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

$𝙻𝙴𝙽$ is the length of the maximum sequence of variables that take the same value that contains the first variable of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ (or 0 if the collection is empty).

Example

(\begin{matrix} 3, 〈\begin{matrix} 𝚟𝚊𝚛 - 4, \\ 𝚟𝚊𝚛 - 4, \\ 𝚟𝚊𝚛 - 4, \\ 𝚟𝚊𝚛 - 5, \\ 𝚟𝚊𝚛 - 5, \\ 𝚟𝚊𝚛 - 4 \end{matrix}〉 \end{matrix})

The $𝚕𝚎𝚗𝚐𝚝𝚑_𝚏𝚒𝚛𝚜𝚝_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint holds since the sequence associated with the first value of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 = 〈 4, 4, 4, 5, 5, 4 〉$ spans over three consecutive variables.

Symmetry

All occurrences of two distinct values of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ can be swapped; all occurrences of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ can be renamed to any unused value.

Reformulation

Without loss of generality let assume that the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 = 〈 V_{1}, V_{2}, ..., V_{n} 〉$ has more than one variable. By introducing $2 \cdot n - 1$ 0-1 variables, the $𝚕𝚎𝚗𝚐𝚝𝚑_𝚏𝚒𝚛𝚜𝚝_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ $(𝙻𝙴𝙽, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ constraint can be expressed in term of $2 \cdot n - 1$ reified constraints and one arithmetic constraint (i.e., a $𝚜𝚞𝚖_𝚌𝚝𝚛$ constraint). We first introduce $n - 1$ variables that are respectively set to 1 if and only if two given consecutive variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are equal:

$B_{1, 2} \Leftrightarrow V_{1} = V_{2}$ ,

$B_{2, 3} \Leftrightarrow V_{2} = V_{3}$ ,

$... ... ... ... ... ...$

$B_{n - 1, n} \Leftrightarrow V_{n - 1} = V_{n}$ .

We then introduce $n$ variables $A_{1}, A_{2}, ..., A_{n}$ that are respectively associated to the different sliding sequences starting on the first variable of the sequence $V_{1} V_{2} ... V_{n}$ . Variable $A_{i}$ is set to 1 if and only if $V_{1} = V_{2} = ... = V_{i}$ :

$A_{1} = 1$ ,

$A_{2} \Leftrightarrow B_{1, 2} \land A_{1},$

$A_{3} \Leftrightarrow B_{2, 3} \land A_{2},$

$... ... ... ... ... ...$

$A_{n} \Leftrightarrow B_{n - 1, n} \land A_{n - 1}$ .

Finally we state the following arithmetic constraint:

$𝙻𝙴𝙽 = A_{1} + A_{2} + ... + A_{n}$ .

Keywords

characteristic of a constraint: automaton, automaton with counters.

combinatorial object: sequence.

constraint network structure: sliding cyclic(1) constraint network(2).

constraint type: value constraint, counting constraint.

Automaton: Figure 5.186.1 depicts the automaton associated with the $𝚕𝚎𝚗𝚐𝚝𝚑_𝚏𝚒𝚛𝚜𝚝_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint. To each pair of consecutive variables $({𝚅𝙰𝚁}_{i}, {𝚅𝙰𝚁}_{i + 1})$ of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a signature variable $𝚂_{i}$ . The following signature constraint links ${𝚅𝙰𝚁}_{i}$ , ${𝚅𝙰𝚁}_{i + 1}$ and $𝚂_{i}$ : ${𝚅𝙰𝚁}_{i} = {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow 𝚂_{i}$ .

Figure 5.186.1. Automaton of the $𝚕𝚎𝚗𝚐𝚝𝚑_𝚏𝚒𝚛𝚜𝚝_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint when $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | \geq 2$

Figure 5.186.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚕𝚎𝚗𝚐𝚝𝚑_𝚏𝚒𝚛𝚜𝚝_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.186. length_first_sequence

Figure 5.186.1. Automaton of the $𝚕𝚎𝚗𝚐𝚝𝚑_𝚏𝚒𝚛𝚜𝚝_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint when $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | \geq 2$

Figure 5.186.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚕𝚎𝚗𝚐𝚝𝚑_𝚏𝚒𝚛𝚜𝚝_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint

W3C: XHTML - last update: 2010-12-6. SD.

Global Constraint Catalog

5. Global Constraint Catalogue

5.186. length_first_sequence

Figure 5.186.1. Automaton of the 𝚕𝚎𝚗𝚐𝚝𝚑_𝚏𝚒𝚛𝚜𝚝_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎 constraint when |𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂|≥2

Figure 5.186.2. Hypergraph of the reformulation corresponding to the automaton of the 𝚕𝚎𝚗𝚐𝚝𝚑_𝚏𝚒𝚛𝚜𝚝_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎 constraint

W3C: XHTML - last update: 2010-12-6. SD.

Figure 5.186.1. Automaton of the $𝚕𝚎𝚗𝚐𝚝𝚑_𝚏𝚒𝚛𝚜𝚝_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint when $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | \geq 2$

Figure 5.186.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚕𝚎𝚗𝚐𝚝𝚑_𝚏𝚒𝚛𝚜𝚝_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint