5.246. max_occ_of_sorted_tuples_of_values

DESCRIPTIONLINKS
Origin

Design.

Constraint

πš–πšŠπš‘_𝚘𝚌𝚌_𝚘𝚏_πšœπš˜πš›πšπšŽπš_πšπšžπš™πš•πšŽπšœ_𝚘𝚏_πšŸπšŠπš•πšžπšŽπšœ(π™Όπ™°πš‡,𝙺,πš…π™΄π™²πšƒπ™Ύπšπš‚)

Type
πš…π™΄π™²πšƒπ™ΎπšπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Arguments
π™Όπ™°πš‡πš’πš—πš
π™Ίπš’πš—πš
πš…π™΄π™²πšƒπ™Ύπšπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟𝚎𝚌-πš…π™΄π™²πšƒπ™Ύπš)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπš,πšŸπšŠπš›)
|πš…π™΄π™²πšƒπ™Ύπš|β‰₯2
πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(πš…π™΄π™²πšƒπ™Ύπš)
π™Όπ™°πš‡β‰₯1
𝙺β‰₯2
𝙺<|πš…π™΄π™²πšƒπ™Ύπš|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπšπš‚,𝚟𝚎𝚌)
|πš…π™΄π™²πšƒπ™Ύπšπš‚|β‰₯1
πšœπšŠπš–πšŽ_πšœπš’πš£πšŽ(πš…π™΄π™²πšƒπ™Ύπšπš‚,𝚟𝚎𝚌)
Purpose

π™Όπ™°πš‡ is equal to the maximum number of occurrences of identical vectors derived from the vectors πš…π™΄π™²πšƒπ™Ύπšπš‚ in the following way. To each vector 〈v 1 ,v 2 ,β‹―,v m βŒͺ of πš…π™΄π™²πšƒπ™Ύπšπš‚ (with v 1 ,v 2 ,β‹―,v m distinct) let 〈s 1 ,s 2 ,β‹―,s m βŒͺ be the corresponding sorted vector by increasing component. We generate all vectors 〈u 1 ,u 2 ,β‹―,u 𝙺 βŒͺ such that u 1 =s i 1 , u 2 =s i 2 , β‹―, u 𝙺 =s i 𝙺 (with 1≀i 1 <i 2 <β‹―<i 𝙺 ≀m).

Example
1,2,𝚟𝚎𝚌-4,2,1,𝚟𝚎𝚌-2,3,5,𝚟𝚎𝚌-3,6,4,𝚟𝚎𝚌-5,4,7,𝚟𝚎𝚌-6,5,1,𝚟𝚎𝚌-7,6,2,𝚟𝚎𝚌-3,1,7

Given the seven vectors of the example we respectively generate:

  • the pairs 〈1,2βŒͺ, 〈1,4βŒͺ and 〈2,4βŒͺ from the triple 〈4,2,1βŒͺ,

  • the pairs 〈2,3βŒͺ, 〈2,5βŒͺ and 〈3,5βŒͺ from the triple 〈2,3,5βŒͺ,

  • the pairs 〈3,4βŒͺ, 〈3,6βŒͺ and 〈4,6βŒͺ from the triple 〈3,6,4βŒͺ,

  • the pairs 〈4,5βŒͺ, 〈4,7βŒͺ and 〈5,7βŒͺ from the triple 〈5,4,7βŒͺ,

  • the pairs 〈1,5βŒͺ, 〈1,6βŒͺ and 〈5,6βŒͺ from the triple 〈6,5,1βŒͺ,

  • the pairs 〈2,6βŒͺ, 〈2,7βŒͺ and 〈6,7βŒͺ from the triple 〈7,6,2βŒͺ,

  • the pairs 〈1,3βŒͺ, 〈1,7βŒͺ and 〈3,7βŒͺ from the triple 〈3,1,7βŒͺ.

Putting these pairs together, we get the set of pairs {〈1,2βŒͺ, 〈1,3βŒͺ, 〈1,4βŒͺ, 〈1,5βŒͺ, 〈1,6βŒͺ, 〈1,7βŒͺ, 〈2,3βŒͺ, 〈2,4βŒͺ, 〈2,5βŒͺ, 〈2,6βŒͺ, 〈2,7βŒͺ, 〈3,4βŒͺ, 〈3,5βŒͺ, 〈3,6βŒͺ, 〈3,7βŒͺ, 〈4,5βŒͺ, 〈4,6βŒͺ, 〈4,7βŒͺ, 〈5,6βŒͺ, 〈5,7βŒͺ, 〈6,7βŒͺ}. The πš–πšŠπš‘_𝚘𝚌𝚌_𝚘𝚏_πšœπš˜πš›πšπšŽπš_πšπšžπš™πš•πšŽπšœ_𝚘𝚏_πšŸπšŠπš•πšžπšŽπšœ constraint holds since each vector has pairwise distinct components, and since π™Όπ™°πš‡ is set to one and all the generated pairs are distinct.

Typical
π™Όπ™°πš‡=1
𝙺+1=|πš…π™΄π™²πšƒπ™Ύπš|
|πš…π™΄π™²πšƒπ™Ύπšπš‚|>2
Arg. properties
  • Functional dependency: π™Όπ™°πš‡ determined by 𝙺 and πš…π™΄π™²πšƒπ™Ύπšπš‚.

  • Contractible wrt. πš…π™΄π™²πšƒπ™Ύπšπš‚ when π™Όπ™°πš‡=1.

Usage

This constraint occurs in balanced block design problems where all vectors are not necessarily sorted.

See also

common keyword: πš–πšŠπš‘_𝚘𝚌𝚌_𝚘𝚏_πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšπšžπš™πš•πšŽπšœ_𝚘𝚏_πšŸπšŠπš•πšžπšŽπšœ, πš–πšŠπš‘_𝚘𝚌𝚌_𝚘𝚏_πšπšžπš™πš•πšŽπšœ_𝚘𝚏_πšŸπšŠπš•πšžπšŽπšœΒ (vector).

implied by: πš–πšŠπš‘_𝚘𝚌𝚌_𝚘𝚏_πšπšžπš™πš•πšŽπšœ_𝚘𝚏_πšŸπšŠπš•πšžπšŽπšœ.

Keywords

characteristic of a constraint: vector.

modelling: functional dependency.