5.245. open_among

DESCRIPTIONLINKSGRAPH
Origin

Derived from πšŠπš–πš˜πš—πš and πš˜πš™πšŽπš—_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’.

Constraint

πš˜πš™πšŽπš—_πšŠπš–πš˜πš—πš(πš‚,π™½πš…π™°πš,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚)

Arguments
πš‚πšœπšŸπšŠπš›
π™½πš…π™°πšπšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°π™»πš„π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš)
Restrictions
πš‚β‰₯1
πš‚β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
π™½πš…π™°πšβ‰₯0
π™½πš…π™°πšβ‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
πšπš’πšœπšπš’πš—πšŒπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
Purpose

Let 𝒱 be the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ for which the corresponding position belongs to the set πš‚. Positions are numbered from 1. π™½πš…π™°πš is the number of variables of 𝒱 that take their value in πš…π™°π™»πš„π™΄πš‚.

Example
{2,3,4,5},3,8,5,5,4,1,1,5,8

The πš˜πš™πšŽπš—_πšŠπš–πš˜πš—πš constraint holds since within the last four values (i.e.,Β πš‚={2,3,4,5}) of 〈8,5,5,4,1βŒͺ exactly 3 values belong to the set of values {1,5,8}.

Symmetries
  • Items of πš…π™°π™»πš„π™΄πš‚ are permutable.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› that belongs to πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• (resp. does not belong to πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•) can be replaced by any other value in πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• (resp. not in πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•).

See also

common keyword: πš˜πš™πšŽπš—_πšŠπšπš•πšŽπšŠπšœπš, πš˜πš™πšŽπš—_πšŠπšπš–πš˜πšœπšΒ (open constraint,value constraint), πš˜πš™πšŽπš—_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (open constraint,counting constraint).

hard version: πšŠπš–πš˜πš—πš.

used in graph description: πš’πš—_𝚜𝚎𝚝.

Keywords

constraint arguments: constraint involving set variables.

constraint type: open constraint, value constraint, counting constraint.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
π‘†πΈπΏπΉβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)

Arc arity
Arc constraint(s)
β€’ πš’πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›,πš…π™°π™»πš„π™΄πš‚)
β€’ πš’πš—_𝚜𝚎𝚝(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πš”πšŽπš’,πš‚)
Graph property(ies)
𝐍𝐀𝐑𝐂=π™½πš…π™°πš

Graph model

The arc constraint corresponds to the conjunction of unary constraints πš’πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›,πš…π™°π™»πš„π™΄πš‚) and πš’πš—_𝚜𝚎𝚝(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πš”πšŽπš’,πš‚) defined in this catalogue. Consequently we employ the 𝑆𝐸𝐿𝐹 arc generator in order to produce an initial graph with a single loop on each vertex.

PartsΒ (A) andΒ (B) of FigureΒ 5.245.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the loops of the final graph are stressed in bold.

Figure 5.245.1. Initial and final graph of the πš˜πš™πšŽπš—_πšŠπš–πš˜πš—πš constraint
ctrs/open_amongActrs/open_amongB
(a) (b)