5.8. all_equal_valley
DESCRIPTION | LINKS | AUTOMATON |
- Origin
- Constraint
- Argument
- Restrictions
- Purpose
A variable of the sequence of variables is a valley if and only if there exists an such that and and .
Enforce all the valleys of the sequence to be assigned the same value, i.e.Β to be located at the same altitude.
- Example
-
The constraint holds since the two valleys, in bold, of the sequence are located at the same altitude 2. FigureΒ 5.8.1 depicts the solution associated with the example.
Figure 5.8.1. Illustration of the Example slot: a sequence of nine variables , , , , , , , , respectively fixed to values 1, 5, 5, 4, 2, 2, 6, 2, 7 and its corresponding two valleys, in red, both located at altitude 2
Note that the constraint does not enforce that the minimum value of the sequence 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 contains at least one valley.
- Typical
- Symmetries
- Arg. properties
Prefix-contractible wrt. .
Suffix-contractible wrt. .
- Counting
-
Length () 2 3 4 5 6 7 8 Solutions 9 64 625 7330 93947 1267790 17908059 Number of solutions for : domains
- See also
-
implies: , .
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.8.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.8.2. Automaton for the constraint (note the conditional transition from state to state testing that the counter is equal to for enforcing that all valleys are located at the same altitude)
Figure 5.8.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 )