5.113. deepest_valley
DESCRIPTION | LINKS | AUTOMATON |
- Origin
- Constraint
- Arguments
- Restriction
- Purpose
A variable of the sequence of variables is a valley if and only if there exists an such that and and . is the minimum value of the valley variables. If no such variable exists is equal to the default value .
- Example
-
The first constraint holds since 2 is the deepest valley of the sequence .
Figure 5.113.1. Illustration of the first example of the Example slot: a sequence of eight variables , , , , , , , respectively fixed to values 5, 3, 4, 8, 8, 2, 7, 1 and its corresponding deepest valley of depth 2
- Typical
- Symmetry
Items of can be reversed.
- Arg. properties
Functional dependency: determined by .
- Counting
-
Length () 2 3 4 5 6 7 8 Solutions 9 64 625 7776 117649 2097152 43046721 Number of solutions for : domains
Length () 2 3 4 5 6 7 8 Total 9 64 625 7776 117649 2097152 43046721 Parameter value 0 - 9 176 2900 50472 976227 21133632 1 - 4 99 1712 29125 540576 11233250 2 - 1 44 900 15680 283250 5665896 3 - - 11 380 7587 138544 2693425 4 - - - 92 3000 61389 1195056 5 - - - - 697 22632 484020 6 - - - - - 5036 166208 7 - - - - - - 35443 1000000 9 50 295 1792 11088 69498 439791 Solution count for : domains
- 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).
- Automaton
FigureΒ 5.113.2 depicts the automaton associated with the constraint. To each pair of consecutive variables of the collection corresponds a signature variable . The following signature constraint links , and :
.
Figure 5.113.2. Automaton of the constraint and its glue matrix (state means that we are in increasing or stationary mode, state means that we are in decreasing mode, a new valley is detected each time we switch from decreasing to increasing mode and the counter is updated accordingly); is the largest integer that can be represented on a machine
Figure 5.113.3. Hypergraph of the reformulation corresponding to the automaton of the constraint ( is set to the largest integer that can be represented on a machine)