5.113. deepest_valley

DESCRIPTIONLINKSAUTOMATON
Origin

Derived from πšŸπšŠπš•πš•πšŽπš’.

Constraint

πšπšŽπšŽπš™πšŽπšœπš_πšŸπšŠπš•πš•πšŽπš’(π™³π™΄π™Ώπšƒπ™·,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Arguments
π™³π™΄π™Ώπšƒπ™·πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restriction
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

A variable V k (1<k<m) of the sequence of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚=V 1 ,β‹―,V m is a valley if and only if there exists an i (1<i≀k) such that V i-1 >V i and V i =V i+1 =β‹―=V k and V k <V k+1 . π™³π™΄π™Ώπšƒπ™· is the minimum value of the valley variables. If no such variable exists π™³π™΄π™Ώπšƒπ™· is equal to the default value π™Όπ™°πš‡π™Έπ™½πšƒ.

Example
(2,5,3,4,8,8,2,7,1)
(7,1,3,4,8,8,8,7,8)

The first πšπšŽπšŽπš™πšŽπšœπš_πšŸπšŠπš•πš•πšŽπš’ constraint holds since 2 is the deepest valley of the sequence 5 3 4 8 8 2 7 1.

Figure 5.113.1. Illustration of the first example of the Example slot: a sequence of eight variables V 1 , V 2 , V 3 , V 4 , V 5 , V 6 , V 7 , V 8 respectively fixed to values 5, 3, 4, 8, 8, 2, 7, 1 and its corresponding deepest valley of depth 2
ctrs/deepest_valley-1-tikz
Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>2
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>2
πšŸπšŠπš•πš•πšŽπš’(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>0
Symmetry

Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ can be reversed.

Arg. properties

Functional dependency: π™³π™΄π™Ώπšƒπ™· determined by πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Counting
Length (n)2345678
Solutions9646257776117649209715243046721

Number of solutions for πšπšŽπšŽπš™πšŽπšœπš_πšŸπšŠπš•πš•πšŽπš’: domains 0..n

ctrs/deepest_valley-2-tikz

ctrs/deepest_valley-3-tikz

Length (n)2345678
Total9646257776117649209715243046721
Parameter
value

0-917629005047297622721133632
1-49917122912554057611233250
2-144900156802832505665896
3--1138075871385442693425
4---923000613891195056
5----69722632484020
6-----5036166208
7------35443
100000095029517921108869498439791

Solution count for πšπšŽπšŽπš™πšŽπšœπš_πšŸπšŠπš•πš•πšŽπš’: domains 0..n

ctrs/deepest_valley-4-tikz

ctrs/deepest_valley-5-tikz

See also

common keyword: πš‘πš’πšπš‘πšŽπšœπš_πš™πšŽπšŠπš”, πšŸπšŠπš•πš•πšŽπš’Β (sequence).

implies: πš‹πšŽπšπš πšŽπšŽπš—_πš–πš’πš—_πš–πšŠπš‘.

Keywords

characteristic of a constraint: maxint, automaton, automaton with counters, automaton with same input symbol.

combinatorial object: sequence.

constraint arguments: reverse of a constraint, pure functional dependency.

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

filtering: glue matrix.

modelling: functional dependency.

Automaton

FigureΒ 5.113.2 depicts the automaton associated with the πšπšŽπšŽπš™πšŽπšœπš_πšŸπšŠπš•πš•πšŽπš’ constraint. To each pair of consecutive variables (πš…π™°πš i ,πš…π™°πš i+1 ) of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a signature variable S i . The following signature constraint links πš…π™°πš i , πš…π™°πš i+1 and S i :

πš…π™°πš i <πš…π™°πš i+1 ⇔S i =0 ∧ πš…π™°πš i =πš…π™°πš i+1 ⇔S i =1 ∧ πš…π™°πš i >πš…π™°πš i+1 ⇔S i =2.

Figure 5.113.2. Automaton of the πšπšŽπšŽπš™πšŽπšœπš_πšŸπšŠπš•πš•πšŽπš’ constraint and its glue matrix (state s means that we are in increasing or stationary mode, state u means that we are in decreasing mode, a new valley is detected each time we switch from decreasing to increasing mode and the counter C is updated accordingly); maxint is the largest integer that can be represented on a machine
ctrs/deepest_valley-6-tikz
Figure 5.113.3. Hypergraph of the reformulation corresponding to the automaton of the πšπšŽπšŽπš™πšŽπšœπš_πšŸπšŠπš•πš•πšŽπš’ constraint (C 0 is set to maxint the largest integer that can be represented on a machine)
ctrs/deepest_valley-10-tikz