Global Constraint Catalog: Csize_max_seq

5.347. size_max_seq_alldifferent

DESCRIPTION

LINKS

GRAPH

Origin

N. Beldiceanu

Constraint

$𝚜𝚒𝚣𝚎_𝚖𝚊𝚡_𝚜𝚎𝚚_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝 (𝚂𝙸𝚉𝙴, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Synonyms

$𝚜𝚒𝚣𝚎_𝚖𝚊𝚡𝚒𝚖𝚊𝚕_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎_𝚊𝚕𝚕𝚍𝚒𝚏𝚏$ , $𝚜𝚒𝚣𝚎_𝚖𝚊𝚡𝚒𝚖𝚊𝚕_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎_𝚊𝚕𝚕𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝$ , $𝚜𝚒𝚣𝚎_𝚖𝚊𝚡𝚒𝚖𝚊𝚕_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ .

Arguments

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

Restrictions

𝚂𝙸𝚉𝙴 \geq 0

𝚂𝙸𝚉𝙴 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

$𝚂𝙸𝚉𝙴$ is the size of the maximal sequence (among all possible sequences of consecutive variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ ) for which the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint holds.

Example

(4, 〈2, 2, 4, 5, 2, 7, 4〉)

(1, 〈2, 2, 2, 2, 2, 2, 2〉)

(2, 〈2, 2, 4, 4, 4, 7, 4〉)

(7, 〈2, 0, 4, 6, 5, 7, 3〉)

The first $𝚜𝚒𝚣𝚎_𝚖𝚊𝚡_𝚜𝚎𝚚_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint holds since the constraint $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 𝚟𝚊𝚛 - 4, 𝚟𝚊𝚛 - 5, 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 7 〉)$ holds and since the following three constraints do not hold:

$𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 4, 𝚟𝚊𝚛 - 5, 𝚟𝚊𝚛 - 2 〉)$ ,
$𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 4, 𝚟𝚊𝚛 - 5, 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 7 〉)$ ,
$𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 𝚟𝚊𝚛 - 4, 𝚟𝚊𝚛 - 5, 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 7, 𝚟𝚊𝚛 - 4 〉)$ .

Typical

𝚂𝙸𝚉𝙴 > 2

𝚂𝙸𝚉𝙴 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚛𝚊𝚗𝚐𝚎

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

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/size_max_seq_alldifferent-1-tikz

ctrs/size_max_seq_alldifferent-2-tikz

Length (

n

)

Total

625

7776

117649

2097152

43046721

Parameter

value

200

1050

5922

34104

208224

300

3480

38640

428400

4981032

120

2520

45360

801360

14028336

720

22680

571200

13728960

5040

221760

7378560

40320

2358720

362880

Solution count for $𝚜𝚒𝚣𝚎_𝚖𝚊𝚡_𝚜𝚎𝚚_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ : domains $0 . . n$

ctrs/size_max_seq_alldifferent-3-tikz

ctrs/size_max_seq_alldifferent-4-tikz

implies: $𝚊𝚝𝚕𝚎𝚊𝚜𝚝_𝚗𝚟𝚊𝚕𝚞𝚎$ .

Keywords

characteristic of a constraint: all different, disequality, hypergraph.

combinatorial object: sequence.

constraint arguments: pure functional dependency.

constraint type: sliding sequence constraint, conditional constraint.

modelling: functional dependency.

Arc input(s): $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$
Arc generator: $𝑃𝐴𝑇𝐻_𝑁$ $\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗$
Arc arity: $*$
Arc constraint(s): $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗)$
Graph property(ies): $𝐍𝐀𝐑𝐂$ $= 𝚂𝙸𝚉𝙴$
Graph model: Note that this is an example of global constraint where the arc constraints do not have the same arity. However they correspond to the same type of constraint.

Global Constraint Catalog

5. Global Constraint Catalogue

5.347. size_max_seq_alldifferent