5.261. min_width_valley
DESCRIPTION | LINKS | AUTOMATON |
- Origin
- Constraint
- Synonym
.
- Arguments
- Restrictions
- Purpose
Given a sequence constraint to be fixed to the width of the smallest valley, or to 0 if no valley exists.
- Example
-
The first constraint holds since the sequence contains two valleys of respective width 5 and 6 (see FigureΒ 5.261.1) and since its argument is fixed to the smallest value 5.
Figure 5.261.1. Illustration of the first example of the Example slot: a sequence of eighteen variables , , , , , , , , , , , , , , , , , respectively fixed to values 3, 3, 5, 5, 4, 2, 2, 3, 4, 6, 6, 5, 5, 5, 5, 5, 5, 6 and its two valleys of width 5 and 6.
- Typical
- Symmetries
- 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 50 295 1792 11088 69498 439791 1 - 14 230 3205 56637 1174398 26327058 2 - - 100 2100 28420 424928 9363060 3 - - - 679 17024 268722 3413256 4 - - - - 4480 130452 2345982 5 - - - - - 29154 968946 6 - - - - - - 188628 Solution count for : domains
- See also
common keyword: Β (sequence).
- Keywords
characteristic of a constraint: automaton, automaton with counters.
combinatorial object: sequence.
constraint arguments: reverse of a constraint, pure functional dependency.
- Automaton
FigureΒ 5.261.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.261.2. Automaton of the constraint: the start of the first potential valley is discovered while triggering the transition from to , the bottom of a valley is discovered while triggering the transition from to , the end of a valley and the start of the next potential valley are discovered while triggering the transition from to ; the counters , and respectively stand for min_width, current and first.
Figure 5.261.3. Glue matrix associated with the automaton of the constraint, where stands for
Β Β Β Β 0
Figure 5.261.4. Illustrating the use of the state pair of the glue matrix for linking with the counters variables obtained after reading the prefix and corresponding suffix of the sequence ; note that the suffix (in pink) is proceed in reverse order; the left (resp.Β right) table shows the initialisation (for ) and the evolution (for ) of the state of the automaton and its counters , and upon reading the prefix (resp.Β the reverse suffix ).
Figure 5.261.5. Hypergraph of the reformulation corresponding to the automaton of the constraint