Global Constraint Catalog: Clongest_increasing

5.237. longest_increasing_sequence

DESCRIPTION

LINKS

AUTOMATON

Origin

constraint on sequences

Constraint

$𝚕𝚘𝚗𝚐𝚎𝚜𝚝_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎 (𝙻, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Synonym

$𝚜𝚒𝚣𝚎_𝚕𝚘𝚗𝚐𝚎𝚜𝚝_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ .

Arguments

$𝙻$	$𝚍𝚟𝚊𝚛$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$

Restrictions

𝙻 \geq 0

𝙻 <

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

Purpose

$𝙻$ is the largest difference between the first and the last value of the maximum increasing sequences of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

A sequence of consecutive variables $X_{i}, X_{i + 1}, \dots, X_{j}$ ( $1 \leq i \leq j \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |$ ) of the collection of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ is a maximum increasing sequence if all the following conditions simultaneously apply:

$X_{i} \leq X_{i + 1} \leq \dots \leq X_{j}$ ,
$i = 1$ or $X_{i - 1} > X_{i}$ ,
$i = | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |$ or $X_{j} > X_{j + 1}$ .

Example

(7, 〈10, 8, 8, 6, 4, 9, 11, 8〉)

(0, 〈10, 8, 7, 5, 4, 3, 1, 0〉)

Figure 5.237.1 gives a graphical representation of the first example of the Example slot with its two maximum increasing sequences in red of respective size 0 and 7. The corresponding $𝚕𝚘𝚗𝚐𝚎𝚜𝚝_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint holds since its first argument $𝙻$ is fixed to the maximum size 7.

Figure 5.237.1. Illustration of the first example of the Example slot: a sequence of eight variables $V_{1}$ , $V_{2}$ , $V_{3}$ , $V_{4}$ , $V_{5}$ , $V_{6}$ , $V_{7}$ , $V_{8}$ respectively fixed to values 10, 8, 8, 6, 4, 9, 11, 8 and its two maximum increasing sequences in red of respective size $8 - 8 = 0$ and $11 - 4 = 7$ .

Typical

𝙻 > 0

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 1

𝚗𝚟𝚊𝚕

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) > 2

Symmetry

One and the same constant can be added to the $𝚟𝚊𝚛$ attribute of all items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Arg. properties

Functional dependency: $𝙻$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Counting

Length ( $n$ )	2	3	4	5	6	7	8
Solutions	9	64	625	7776	117649	2097152	43046721

Number of solutions for $𝚕𝚘𝚗𝚐𝚎𝚜𝚝_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ : domains $0 . . n$

ctrs/longest_increasing_sequence-2-tikz

ctrs/longest_increasing_sequence-3-tikz

Length (

n

)

Total

625

7776

117649

2097152

43046721

Parameter

value

252

924

3432

12870

122

750

4412

25382

144314

161

1398

11361

89132

685090

162

1942

20816

211106

2074365

110

2024

28930

375084

4603682

1410

30134

506766

7792840

21072

522648

10197174

363602

10379696

7156690

Solution count for $𝚕𝚘𝚗𝚐𝚎𝚜𝚝_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ : domains $0 . . n$

ctrs/longest_increasing_sequence-4-tikz

ctrs/longest_increasing_sequence-5-tikz

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.

filtering: glue matrix.

modelling: functional dependency.

Automaton: Figure 5.237.2 depicts the automaton associated with the $𝚕𝚘𝚗𝚐𝚎𝚜𝚝_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint.

Figure 5.237.2. Automaton of the $𝚕𝚘𝚗𝚐𝚎𝚜𝚝_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint and its glue matrix (note that the reverse of the $𝚕𝚘𝚗𝚐𝚎𝚜𝚝_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint is the $𝚕𝚘𝚗𝚐𝚎𝚜𝚝_𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint)

Figure 5.237.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚕𝚘𝚗𝚐𝚎𝚜𝚝_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.237. longest_increasing_sequence

Figure 5.237.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚕𝚘𝚗𝚐𝚎𝚜𝚝_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.237. longest_increasing_sequence

Figure 5.237.1. Illustration of the first example of the Example slot: a sequence of eight variables V 1 , V 2 , V 3 , V 4 , V 5 , V 6 , V 7 , V 8 respectively fixed to values 10, 8, 8, 6, 4, 9, 11, 8 and its two maximum increasing sequences in red of respective size 8-8=0 and 11-4=7.

Figure 5.237.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚕𝚘𝚗𝚐𝚎𝚜𝚝_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎 constraint

Figure 5.237.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚕𝚘𝚗𝚐𝚎𝚜𝚝_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ constraint