## 5.8. all_equal_valley

Origin
Constraint

$\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi ’}\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Argument
 $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$
Restrictions
 $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>0$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$
Purpose

A variable ${V}_{k}$ $\left(1 of the sequence of variables $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }={V}_{1},\beta ―,{V}_{m}$ is a valley if and only if there exists an $i$ $\left(1 such that ${V}_{i-1}>{V}_{i}$ and ${V}_{i}={V}_{i+1}=\beta ―={V}_{k}$ and ${V}_{k}<{V}_{k+1}$.

Enforce all the valleys of the sequence $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ to be assigned the same value, i.e.Β to be located at the same altitude.

Example
$\left(β©1,5,5,4,2,2,6,2,7βͺ\right)$

The $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi ’}$ constraint holds since the two valleys, in bold, of the sequence $155422627$ are located at the same altitude 2. FigureΒ 5.8.1 depicts the solution associated with the example.

Note that the $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi ’}$ constraint does not enforce that the minimum value of the sequence $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ corresponds to the altitude of its valleys since, as shown by the example, the sequence can starts with an increasing subsequence that start below the altitude of its valleys. It also does not enforce that the sequence $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ contains at least one valley.

Typical
 $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|\beta ₯5$ $\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)>1$ $\mathrm{\pi \pi \pi \pi \pi \pi ’}$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)\beta ₯2$
Symmetries
• Items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ can be reversed.

• One and the same constant can be added to the $\mathrm{\pi \pi \pi }$ attribute of all items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Arg. properties
• Prefix-contractible wrt. $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

• Suffix-contractible wrt. $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 9 64 625 7330 93947 1267790 17908059

Number of solutions for $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi ’}$: domains $0..n$

Keywords
Cond. implications

$\beta ’$ $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi ’}\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Β Β Β  withΒ  $\mathrm{\pi \pi \pi \pi \pi \pi ’}$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)>1$

Β Β implies $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$.

$\beta ’$ $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi ’}\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Β Β Β  withΒ  $\mathrm{\pi \pi \pi \pi \pi \pi ’}$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)>0$

Β Β implies $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$.

Automaton

FigureΒ 5.8.2 depicts the automaton associated with the $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi ’}$ constraint. To each pair of consecutive variables $\left({\mathrm{\pi  \pi °\pi }}_{i},{\mathrm{\pi  \pi °\pi }}_{i+1}\right)$ of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ corresponds a signature variable ${S}_{i}$. The following signature constraint links ${\mathrm{\pi  \pi °\pi }}_{i}$, ${\mathrm{\pi  \pi °\pi }}_{i+1}$ and ${S}_{i}$: $\left({\mathrm{\pi  \pi °\pi }}_{i}<{\mathrm{\pi  \pi °\pi }}_{i+1}\beta {S}_{i}=0\right)\beta §\left({\mathrm{\pi  \pi °\pi }}_{i}={\mathrm{\pi  \pi °\pi }}_{i+1}\beta {S}_{i}=1\right)\beta §\left({\mathrm{\pi  \pi °\pi }}_{i}>{\mathrm{\pi  \pi °\pi }}_{i+1}\beta {S}_{i}=2\right)$.