## 5.377. stretch_path_partition

Origin
Constraint

$\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}_\mathrm{𝚙𝚊𝚝𝚑}_\mathrm{𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}\right)$

Synonym

$\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}$.

Type
 $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚕}-\mathrm{𝚒𝚗𝚝}\right)$
Arguments
 $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(𝚙-\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂},\mathrm{𝚕𝚖𝚒𝚗}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚕𝚖𝚊𝚡}-\mathrm{𝚒𝚗𝚝}\right)$
Restrictions
 $|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|\ge 1$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂},\mathrm{𝚟𝚊𝚕}\right)$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂},\mathrm{𝚟𝚊𝚕}\right)$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>0$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$ $|\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}|>0$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂},\left[𝚙,\mathrm{𝚕𝚖𝚒𝚗},\mathrm{𝚕𝚖𝚊𝚡}\right]\right)$ $\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}.\mathrm{𝚕𝚖𝚒𝚗}\ge 0$ $\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}.\mathrm{𝚕𝚖𝚒𝚗}\le \mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}.\mathrm{𝚕𝚖𝚊𝚡}$ $\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}.\mathrm{𝚕𝚖𝚒𝚗}\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$
Purpose

In order to define the meaning of the $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}_\mathrm{𝚙𝚊𝚝𝚑}_\mathrm{𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$ constraint, we first introduce the notions of stretch and span. Let $n$ be the number of variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$. Let ${X}_{i},\cdots ,{X}_{j}$ $\left(1\le i\le j\le n\right)$ be consecutive variables of the collection of variables $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ such that the following conditions apply:

• All variables ${X}_{i},\cdots ,{X}_{j}$ take their values in the same partition of the $\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}$ collection (i.e., $\exists l\in \left[1,|\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}|\right]$ such that $\forall k\in \left[i,j\right]:{X}_{k}\in \mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}\left[l\right].p$),

• $i=1$ or ${X}_{i-1}$ is different from ${X}_{i}$,

• $j=n$ or ${X}_{j+1}$ is different from ${X}_{j}$.

We call such a set of variables a stretch. The span of the stretch is equal to $j-i+1$, while the value of the stretch is $l$. We now define the condition enforced by the $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}_\mathrm{𝚙𝚊𝚝𝚑}_\mathrm{𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$ constraint.

Each item $\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}\left[l\right]=\left(𝚙-\mathrm{𝑣𝑎𝑙𝑢𝑒𝑠},\mathrm{𝚕𝚖𝚒𝚗}-s,\mathrm{𝚕𝚖𝚊𝚡}-t\right)$ of the $\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}$ collection enforces the minimum value $s$ as well as the maximum value $t$ for the span of a stretch of value $l$ over consecutive variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection.

Note that:

1. Having an item $\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}\left[l\right]=\left(𝚙-\mathrm{𝑣𝑎𝑙𝑢𝑒𝑠},\mathrm{𝚕𝚖𝚒𝚗}-s,\mathrm{𝚕𝚖𝚊𝚡}-t\right)$ with $s$ strictly greater than 0 does not mean that values of $\mathrm{𝑣𝑎𝑙𝑢𝑒𝑠}$ should be assigned to one of the variables of collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$. It rather means that, when a value of $\mathrm{𝑣𝑎𝑙𝑢𝑒𝑠}$ is used, all stretches of value $l$ must have a span that belong to interval $\left[s,t\right]$.

2. A variable of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ may be assigned a value that is not defined in the attribute $𝚙$ of the $\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}$ collection.

Example
$\left(\begin{array}{c}〈1,2,0,0,2,2,2,0〉,\hfill \\ 〈\begin{array}{ccc}𝚙-〈1,2〉\hfill & \mathrm{𝚕𝚖𝚒𝚗}-2\hfill & \mathrm{𝚕𝚖𝚊𝚡}-4,\hfill \\ 𝚙-〈3〉\hfill & \mathrm{𝚕𝚖𝚒𝚗}-0\hfill & \mathrm{𝚕𝚖𝚊𝚡}-2\hfill \end{array}〉\hfill \end{array}\right)$

The $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}_\mathrm{𝚙𝚊𝚝𝚑}_\mathrm{𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$ constraint holds since the sequence $12002220$ contains two stretches $12$, and $222$ respectively verifying the following conditions:

• The span of the first stretch $12$ is located within interval $\left[2,4\right]$ (i.e., the limit associated with item $\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}\left[1\right]$).

• The span of the second stretch $222$ is located within interval $\left[2,4\right]$ (i.e., the limit associated with item $\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}\left[1\right]$).

Typical
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>1$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>|\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}|$ $|\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}|>1$ $\mathrm{𝚜𝚞𝚖}$$\left(\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}.\mathrm{𝚕𝚖𝚒𝚗}\right)\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}.\mathrm{𝚕𝚖𝚊𝚡}\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$
Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ can be reversed.

• Items of $\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}$ are permutable.

• Items of $\mathrm{𝙿𝙰𝚁𝚃𝙻𝙸𝙼𝙸𝚃𝚂}.𝚙$ are permutable.

• All occurrences of two distinct tuples of values in $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ or $\mathrm{𝙿𝙰𝚁𝙻𝙸𝙼𝙸𝚃𝚂}.𝚙.\mathrm{𝚟𝚊𝚕}$ can be swapped; all occurrences of a tuple of values in $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ or $\mathrm{𝙿𝙰𝚁𝙻𝙸𝙼𝙸𝚃𝚂}.𝚙.\mathrm{𝚟𝚊𝚕}$ can be renamed to any unused tuple of values.

specialisation: $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}_\mathrm{𝚙𝚊𝚝𝚑}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}\in \mathrm{𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$).