5.187. length_last_sequence

DESCRIPTIONLINKSAUTOMATON
Origin

Inspired by πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘

Constraint

πš•πšŽπš—πšπšπš‘_πš•πšŠπšœπš_πšœπšŽπššπšžπšŽπš—πšŒπšŽ(𝙻𝙴𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Arguments
π™»π™΄π™½πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
𝙻𝙴𝙽β‰₯0
𝙻𝙴𝙽≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

𝙻𝙴𝙽 is the length of the maximum sequence of variables that take the same value that contains the last variable of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ (or 0 if the collection is empty).

Example
1,πšŸπšŠπš›-4,πšŸπšŠπš›-4,πšŸπšŠπš›-4,πšŸπšŠπš›-5,πšŸπšŠπš›-5,πšŸπšŠπš›-4

The πš•πšŽπš—πšπšπš‘_πš•πšŠπšœπš_πšœπšŽπššπšžπšŽπš—πšŒπšŽ constraint holds since the sequence associated with the last value of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚=〈4,4,4,5,5,4βŒͺ spans over one single variable.

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Β·n-1 0-1 variables, the πš•πšŽπš—πšπšπš‘_πš•πšŠπšœπš_πšœπšŽπššπšžπšŽπš—πšŒπšŽ(𝙻𝙴𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) constraint can be expressed in term of 2Β·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 n-1,n ⇔V n-1 =V n ,

Β Β Β B n-2,n-1 ⇔V n-2 =V n-1 ,

Β Β Β ...........................

Β Β Β B 1,2 ⇔V 1 =V 2 .

We then introduce n variables A n ,A n-1 ,...,A 1 that are respectively associated to the different sliding sequences ending on the last variable of the sequence V 1 V 2 ... V n . Variable A i is set to 1 if and only if V n =V n-1 =...=V i :

Β Β Β A n =1,

Β Β Β A n-1 ⇔B n-1,n ∧A n ,

Β Β Β A n-2 ⇔B n-2,n-1 ∧A n-1 ,

Β Β Β ...........................

Β Β Β A 1 ⇔B 1,2 ∧A 2 .

Finally we state the following arithmetic constraint:

   𝙻𝙴𝙽=A n +A n-1 +...+A 1 .

See also

common keyword: πš•πšŽπš—πšπšπš‘_πšπš’πš›πšœπš_πšœπšŽπššπšžπšŽπš—πšŒπšŽΒ (counting constraint,sequence).

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.187.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 β‡”πš‚ i .

Figure 5.187.1. Automaton of the πš•πšŽπš—πšπšπš‘_πš•πšŠπšœπš_πšœπšŽπššπšžπšŽπš—πšŒπšŽ constraint when |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|β‰₯2
ctrs/length_last_sequence1
Figure 5.187.2. Hypergraph of the reformulation corresponding to the automaton of the πš•πšŽπš—πšπšπš‘_πš•πšŠπšœπš_πšœπšŽπššπšžπšŽπš—πšŒπšŽ constraint
ctrs/length_last_sequence2