5.189. increasing_peak
DESCRIPTION | LINKS | AUTOMATON |
- Origin
- Constraint
- Argument
- Restrictions
- Purpose
A variable of the sequence of variables is a peak if and only if there exists an such that and and .
When considering all the peaks of the sequence from left to right enforce all peaks to be increasing, i.e.Β the altitude of each peak is greater than or equal to the altitude of its preceding peak when it exists.
- Example
-
The constraint holds since the sequence contains three peaks, in bold, that are increasing.
Figure 5.189.1. Illustration of the Example slot: a sequence of ten variables , , , , , , , , , respectively fixed to values 1, 5, 5, 4, 3, 5, 2, 2, 7, 4 and its corresponding three peaks, in red, respectively located at altitudes 5, 5 and 7
- Typical
- Symmetry
One and the same constant can be added to the attribute of all items of .
- Arg. properties
Prefix-contractible wrt. .
Suffix-contractible wrt. .
- Counting
-
Length () 2 3 4 5 6 7 8 Solutions 9 64 625 7553 105798 1666878 29090469 Number of solutions for : domains
- See also
-
related: , .
- Keywords
characteristic of a constraint: automaton, automaton with counters, automaton with same input symbol.
combinatorial object: sequence.
constraint network structure: sliding cyclic(1) constraint network(2).
- Cond. implications
- Automaton
FigureΒ 5.189.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.189.2. Automaton for the constraint (note the conditional transition from state to state testing that the counter is less than or equal to for enforcing that all peaks from left to right are in increasing altitude)
Figure 5.189.3. Hypergraph of the reformulation corresponding to the automaton of the constraint where stands for the value of the counter (since all states of the automaton are accepting there is no restriction on the last variable )