5.230. no_peak

DESCRIPTIONLINKSAUTOMATON
Origin

Derived from πš™πšŽπšŠπš”.

Constraint

πš—πš˜_πš™πšŽπšŠπš”(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Argument
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

A variable V k (1<k<m) of the sequence of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚=V 1 ,...,V m is a peak if and only if there exists an i (1<i≀k) such that V i-1 <V i and V i =V i+1 =...=V k and V k >V k+1 . The total number of peaks of the sequence of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ is equal to 0.

Example
(1,1,4,8,8)

The πš—πš˜_πš™πšŽπšŠπš” constraint holds since the sequence 1 1 4 8 8 does not contain any peak.

Figure 5.230.1. A sequence without any peak
ctrs/no_peak1
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ can be reversed.

  • One and the same constant can be added to the πšŸπšŠπš› attribute of all items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

See also

comparison swapped: πš—πš˜_πšŸπšŠπš•πš•πšŽπš’.

generalisation: πš™πšŽπšŠπš”Β (introduce a πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ counting the number of peaks).

implied by: πšπšŽπšŒπš›πšŽπšŠπšœπš’πš—πš, πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš.

related: πšŸπšŠπš•πš•πšŽπš’.

Keywords

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint.

combinatorial object: sequence.

constraint network structure: sliding cyclic(1) constraint network(1).

Automaton

FigureΒ 5.230.2 depicts the automaton associated with the πš—πš˜_πš™πšŽπšŠπš” constraint. To each pair of consecutive variables (πš…π™°πš i ,πš…π™°πš i+1 ) of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a signature variable πš‚ i . The following signature constraint links πš…π™°πš i , πš…π™°πš i+1 and πš‚ i : (πš…π™°πš i <πš…π™°πš i+1 β‡”πš‚ i =0) ∧ (πš…π™°πš i =πš…π™°πš i+1 β‡”πš‚ i =1) ∧ (πš…π™°πš i >πš…π™°πš i+1 β‡”πš‚ i =2).

Figure 5.230.2. Automaton of the πš—πš˜_πš™πšŽπšŠπš” constraint
ctrs/no_peak2
Figure 5.230.3. Hypergraph of the reformulation corresponding to the automaton of the πš—πš˜_πš™πšŽπšŠπš” constraint
ctrs/no_peak3