5.125. elements_alldifferent

DESCRIPTIONLINKSGRAPH
Origin

Derived from πšŽπš•πšŽπš–πšŽπš—πšπšœ and πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

Constraint

πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(π™Έπšƒπ™΄π™Όπš‚,πšƒπ™°π™±π™»π™΄)

Synonyms

πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšŠπš•πš•πšπš’πšπš, πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš.

Arguments
π™Έπšƒπ™΄π™Όπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πšπšŸπšŠπš›,πšŸπšŠπš•πšžπšŽ-πšπšŸπšŠπš›)
πšƒπ™°π™±π™»π™΄πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,πšŸπšŠπš•πšžπšŽ-πšπšŸπšŠπš›)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(π™Έπšƒπ™΄π™Όπš‚,[πš’πš—πšπšŽπš‘,πšŸπšŠπš•πšžπšŽ])
π™Έπšƒπ™΄π™Όπš‚.πš’πš—πšπšŽπš‘β‰₯1
π™Έπšƒπ™΄π™Όπš‚.πš’πš—πšπšŽπš‘β‰€|πšƒπ™°π™±π™»π™΄|
|π™Έπšƒπ™΄π™Όπš‚|=|πšƒπ™°π™±π™»π™΄|
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπ™°π™±π™»π™΄,[πš’πš—πšπšŽπš‘,πšŸπšŠπš•πšžπšŽ])
πšƒπ™°π™±π™»π™΄.πš’πš—πšπšŽπš‘β‰₯1
πšƒπ™°π™±π™»π™΄.πš’πš—πšπšŽπš‘β‰€|πšƒπ™°π™±π™»π™΄|
πšπš’πšœπšπš’πš—πšŒπš(πšƒπ™°π™±π™»π™΄,πš’πš—πšπšŽπš‘)
Purpose

All the items of the π™Έπšƒπ™΄π™Όπš‚ collection should be equal to one of the entries of the table πšƒπ™°π™±π™»π™΄ and all the variables π™Έπšƒπ™΄π™Όπš‚.πš’πš—πšπšŽπš‘ should take distinct values.

Example
πš’πš—πšπšŽπš‘-2πšŸπšŠπš•πšžπšŽ-9,πš’πš—πšπšŽπš‘-1πšŸπšŠπš•πšžπšŽ-6,πš’πš—πšπšŽπš‘-4πšŸπšŠπš•πšžπšŽ-9,πš’πš—πšπšŽπš‘-3πšŸπšŠπš•πšžπšŽ-2,πš’πš—πšπšŽπš‘-1πšŸπšŠπš•πšžπšŽ-6,πš’πš—πšπšŽπš‘-2πšŸπšŠπš•πšžπšŽ-9,πš’πš—πšπšŽπš‘-3πšŸπšŠπš•πšžπšŽ-2,πš’πš—πšπšŽπš‘-4πšŸπšŠπš•πšžπšŽ-9

The πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint holds since, as depicted by FigureΒ 5.125.1, there is a one to one correspondence between the items of the π™Έπšƒπ™΄π™Όπš‚ collection and the items of the πšƒπ™°π™±π™»π™΄ collection.

Figure 5.125.1. Illustration of the one to one correspondence between the items of π™Έπšƒπ™΄π™Όπš‚ and the items of πšƒπ™°π™±π™»π™΄
ctrs/elements_alldifferent1
Typical
|π™Έπšƒπ™΄π™Όπš‚|>1
πš›πšŠπš—πšπšŽ(π™Έπšƒπ™΄π™Όπš‚.πšŸπšŠπš•πšžπšŽ)>1
|πšƒπ™°π™±π™»π™΄|>1
πš›πšŠπš—πšπšŽ(πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ)>1
Symmetries
  • Arguments are permutable w.r.t. permutation (π™Έπšƒπ™΄π™Όπš‚,πšƒπ™°π™±π™»π™΄).

  • Items of π™Έπšƒπ™΄π™Όπš‚ are permutable.

  • Items of πšƒπ™°π™±π™»π™΄ are permutable.

  • All occurrences of two distinct values in π™Έπšƒπ™΄π™Όπš‚.πšŸπšŠπš•πšžπšŽ or πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ can be swapped; all occurrences of a value in π™Έπšƒπ™΄π™Όπš‚.πšŸπšŠπš•πšžπšŽ or πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ can be renamed to any unused value.

Usage

Used for replacing by one single πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint an πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš and a set of πšŽπš•πšŽπš–πšŽπš—πš constraints having the following structure:

For instance, the constraint given in the Example slot is equivalent to the conjunction of the following set of constraints:

πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(βŒ©πšŸπšŠπš›-2,πšŸπšŠπš›-1,πšŸπšŠπš›-4,πšŸπšŠπš›-3βŒͺ)
πšŽπš•πšŽπš–πšŽπš—πšπš’πš—πšπšŽπš‘-2πšŸπšŠπš•πšžπšŽ-9,πš’πš—πšπšŽπš‘-1πšŸπšŠπš•πšžπšŽ-6,πš’πš—πšπšŽπš‘-2πšŸπšŠπš•πšžπšŽ-9,πš’πš—πšπšŽπš‘-3πšŸπšŠπš•πšžπšŽ-2,πš’πš—πšπšŽπš‘-4πšŸπšŠπš•πšžπšŽ-9
πšŽπš•πšŽπš–πšŽπš—πšπš’πš—πšπšŽπš‘-1πšŸπšŠπš•πšžπšŽ-6,πš’πš—πšπšŽπš‘-1πšŸπšŠπš•πšžπšŽ-6,πš’πš—πšπšŽπš‘-2πšŸπšŠπš•πšžπšŽ-9,πš’πš—πšπšŽπš‘-3πšŸπšŠπš•πšžπšŽ-2,πš’πš—πšπšŽπš‘-4πšŸπšŠπš•πšžπšŽ-9
πšŽπš•πšŽπš–πšŽπš—πšπš’πš—πšπšŽπš‘-3πšŸπšŠπš•πšžπšŽ-2,πš’πš—πšπšŽπš‘-1πšŸπšŠπš•πšžπšŽ-6,πš’πš—πšπšŽπš‘-2πšŸπšŠπš•πšžπšŽ-9,πš’πš—πšπšŽπš‘-3πšŸπšŠπš•πšžπšŽ-2,πš’πš—πšπšŽπš‘-4πšŸπšŠπš•πšžπšŽ-9
πšŽπš•πšŽπš–πšŽπš—πšπš’πš—πšπšŽπš‘-4πšŸπšŠπš•πšžπšŽ-9,πš’πš—πšπšŽπš‘-1πšŸπšŠπš•πšžπšŽ-6,πš’πš—πšπšŽπš‘-2πšŸπšŠπš•πšžπšŽ-9,πš’πš—πšπšŽπš‘-3πšŸπšŠπš•πšžπšŽ-2,πš’πš—πšπšŽπš‘-4πšŸπšŠπš•πšžπšŽ-9

As a practical example of utilisation of the πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint we show how to model the link between a permutation consisting of one single cycle and its expanded form. For instance, to the permutation 3,6,5,2,4,1 corresponds the sequence 3 5 4 2 6 1. Let us note S 1 ,S 2 ,S 3 ,S 4 ,S 5 ,S 6 the permutation and V 1 V 2 V 3 V 4 V 5 V 6 its expanded form (see FigureΒ 5.125.2).

The constraint:

πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšπš’πš—πšπšŽπš‘-V 1 πšŸπšŠπš•πšžπšŽ-V 2 ,πš’πš—πšπšŽπš‘-V 2 πšŸπšŠπš•πšžπšŽ-V 3 ,πš’πš—πšπšŽπš‘-V 3 πšŸπšŠπš•πšžπšŽ-V 4 ,πš’πš—πšπšŽπš‘-V 4 πšŸπšŠπš•πšžπšŽ-V 5 ,πš’πš—πšπšŽπš‘-V 5 πšŸπšŠπš•πšžπšŽ-V 6 ,πš’πš—πšπšŽπš‘-V 6 πšŸπšŠπš•πšžπšŽ-V 1 ,πš’πš—πšπšŽπš‘-1πšŸπšŠπš•πšžπšŽ-S 1 ,πš’πš—πšπšŽπš‘-2πšŸπšŠπš•πšžπšŽ-S 2 ,πš’πš—πšπšŽπš‘-3πšŸπšŠπš•πšžπšŽ-S 3 ,πš’πš—πšπšŽπš‘-4πšŸπšŠπš•πšžπšŽ-S 4 ,πš’πš—πšπšŽπš‘-5πšŸπšŠπš•πšžπšŽ-S 5 ,πš’πš—πšπšŽπš‘-6πšŸπšŠπš•πšžπšŽ-S 6

models the fact that S 1 ,S 2 ,S 3 ,S 4 ,S 5 ,S 6 corresponds to a permutation with one single cycle. It also expresses the link between the variables S 1 ,S 2 ,S 3 ,S 4 ,S 5 ,S 6 and V 1 ,V 2 ,V 3 ,V 4 ,V 5 ,V 6 .

Figure 5.125.2. Two representations of a permutation containing one single cycle
ctrs/elements_alldifferent2
Reformulation

The πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(βŒ©πš’πš—πšπšŽπš‘-I 1 πšŸπšŠπš•πšžπšŽ-V 1 ,πš’πš—πšπšŽπš‘-I 2 πšŸπšŠπš•πšžπšŽ-V 2 ,...,πš’πš—πšπšŽπš‘-I |π™Έπšƒπ™΄π™Όπš‚| πšŸπšŠπš•πšžπšŽ-V |π™Έπšƒπ™΄π™Όπš‚| βŒͺ,πšƒπ™°π™±π™»π™΄) constraint can be expressed in term of a conjunction of |π™Έπšƒπ™΄π™Όπš‚| πšŽπš•πšŽπš– constraints and of one πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint of the form:

Β Β Β πšŽπš•πšŽπš–(βŒ©πš’πš—πšπšŽπš‘-I 1 πšŸπšŠπš•πšžπšŽ-V 1 βŒͺ,πšƒπ™°π™±π™»π™΄),

Β Β Β πšŽπš•πšŽπš–(βŒ©πš’πš—πšπšŽπš‘-I 2 πšŸπšŠπš•πšžπšŽ-V 2 βŒͺ,πšƒπ™°π™±π™»π™΄),

Β Β Β ...

Β Β Β πšŽπš•πšŽπš–(βŒ©πš’πš—πšπšŽπš‘-I |π™Έπšƒπ™΄π™Όπš‚| πšŸπšŠπš•πšžπšŽ-V |π™Έπšƒπ™΄π™Όπš‚| βŒͺ,πšƒπ™°π™±π™»π™΄),

Β Β Β πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(〈I 1 ,I 2 ,...,I |π™Έπšƒπ™΄π™Όπš‚| βŒͺ).

See also

implies: πšŽπš•πšŽπš–πšŽπš—πšπšœ.

used in reformulation: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πšŽπš•πšŽπš–, πšŽπš•πšŽπš–πšŽπš—πš.

Keywords

characteristic of a constraint: disequality.

combinatorial object: permutation.

constraint type: data constraint.

modelling: array constraint, table, functional dependency.

Arc input(s)

π™Έπšƒπ™΄π™Όπš‚ πšƒπ™°π™±π™»π™΄

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πšπšŽπš–πšœ,πšπšŠπš‹πš•πšŽ)

Arc arity
Arc constraint(s)
β€’ πš’πšπšŽπš–πšœ.πš’πš—πšπšŽπš‘=πšπšŠπš‹πš•πšŽ.πš’πš—πšπšŽπš‘
β€’ πš’πšπšŽπš–πšœ.πšŸπšŠπš•πšžπšŽ=πšπšŠπš‹πš•πšŽ.πšŸπšŠπš•πšžπšŽ
Graph property(ies)
𝐍𝐕𝐄𝐑𝐓𝐄𝐗=|π™Έπšƒπ™΄π™Όπš‚|+|πšƒπ™°π™±π™»π™΄|

Graph model

The fact that all variables π™Έπšƒπ™΄π™Όπš‚.πš’πš—πšπšŽπš‘ are pairwise different is derived from the conjunctions of the following facts:

  • From the graph property 𝐍𝐕𝐄𝐑𝐓𝐄𝐗=|π™Έπšƒπ™΄π™Όπš‚|+|πšƒπ™°π™±π™»π™΄| it follows that all vertices of the initial graph belong also to the final graph,

  • A vertex v belongs to the final graph if there is at least one constraint involving v that holds,

  • From the first condition πš’πšπšŽπš–πšœ.πš’πš—πšπšŽπš‘=πšπšŠπš‹πš•πšŽ.πš’πš—πšπšŽπš‘ of the arc constraint, and from the restriction πšπš’πšœπšπš’πš—πšŒπš(πšƒπ™°π™±π™»π™΄.πš’πš—πšπšŽπš‘) it follows: for all vertices v generated from the collection π™Έπšƒπ™΄π™Όπš‚ at most one constraint involving v holds.

PartsΒ (A) andΒ (B) of FigureΒ 5.125.3 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 graph property, the vertices of the final graph are stressed in bold.

Figure 5.125.3. Initial and final graph of the πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint
ctrs/elements_alldifferentActrs/elements_alldifferentB
(a) (b)
Signature

Since the final graph cannot have more than |π™Έπšƒπ™΄π™Όπš‚|+|πšƒπ™°π™±π™»π™΄| vertices one can simplify 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Β― Μ² to 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Β―.