5.193. inflexion
DESCRIPTION | LINKS | AUTOMATON |
- Origin
N.Β Beldiceanu
- Constraint
- Arguments
- Restrictions
- Purpose
is equal to the number of times that the following conjunctions of constraints hold:
,
,
.
where is the item of the collection and , , and is or .
- Example
-
The first constraint holds since the sequence contains three inflexions peaks that respectively correspond to values 8, 2 and 7.
Figure 5.193.1. Illustration of the first example of the Example slot: a sequence of eight variables , , , , , , , respectively fixed to values 1, 1, 4, 8, 8, 2, 7, 1 and its three inflexions in red, two peaks and one valley ()
- All solutions
FigureΒ 5.193.2 gives all solutions to the following non ground instance of the constraint: , , , , , , .
Figure 5.193.2. All solutions corresponding to the non ground example of the constraint of the All solutions slot where each inflexion (i.e.Β peak or valley) is coloured in orange or cyan
- Typical
- Symmetries
- Arg. properties
Functional dependency: determined by .
- Usage
Useful for constraining the number of inflexions of a sequence of domain variables.
- Remark
Since the arity of the arc constraint is not fixed, the constraint cannot be currently described with the graph-based representation. However, this would not hold anymore if we were introducing a slot that specifies how to merge adjacent vertices of the final graph.
- 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 36 135 498 1841 6856 25731 1 - 28 320 2588 18494 125284 828120 2 - - 170 3348 44058 492320 5069970 3 - - - 1342 40446 778936 12341184 4 - - - - 12810 549152 14547186 5 - - - - - 144604 8354520 6 - - - - - - 1880010 Solution count for : domains
- See also
common keyword: , , , Β (sequence).
- Keywords
characteristic of a constraint: 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).
- Cond. implications
- Automaton
FigureΒ 5.193.3 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.193.3. Automaton of the constraint (state means that we are in stationary mode, state means that we are in increasing mode, state means that we are in decreasing mode, a new inflexion is detected each time we switch from increasing to decreasing mode β or conversely from decreasing to increasing mode β and the counter is incremented accordingly)
Figure 5.193.4. Hypergraph of the reformulation corresponding to the automaton of the constraint
Figure 5.193.5. Glue matrix associated with the automaton of the constraint
Β Β Β 0
Β Β Β
Β Β Β
Β Β Β
Β Β Β
Figure 5.193.6. 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 counter upon reading the prefix (resp.Β the reverse suffix ).