5.21. alldifferent_same_value

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

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

Constraint

πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšœπšŠπš–πšŽ_πšŸπšŠπš•πšžπšŽ(π™½πš‚π™°π™Όπ™΄,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2)

Synonyms

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

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

All the values assigned to the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 are pairwise distinct. π™½πš‚π™°π™Όπ™΄ is equal to number of constraints of the form πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1[i].πšŸπšŠπš›=πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2[i].πšŸπšŠπš› (1≀i≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|) that hold.

Example
(2,7,3,1,5,1,3,1,7)

The πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšœπšŠπš–πšŽ_πšŸπšŠπš•πšžπšŽ constraint holds since:

  • All the values 7, 3, 1 and 5 are distinct,

  • Among the four expressions 7=1, 3=3, 1=1 and 5=7 exactly 2 conditions hold.

Typical
π™½πš‚π™°π™Όπ™΄<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|>2
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 are permutable (same permutation used).

  • All occurrences of two distinct values in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.πšŸπšŠπš› or πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.πšŸπšŠπš› can be swapped; all occurrences of a value in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.πšŸπšŠπš› or πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.πšŸπšŠπš› can be renamed to any unused value.

Arg. properties

Functional dependency: π™½πš‚π™°π™Όπ™΄ determined by πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.

Usage

When all variables of the second collection are initially bound to distinct values the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšœπšŠπš–πšŽ_πšŸπšŠπš•πšžπšŽ constraint can be explained in the following way:

  • We interpret the variables of the second collection as the previous solution to a problem where all variables have to be distinct.

  • We interpret the variables of the first collection as the current solution to find, where all variables should again be pairwise distinct.

The variable π™½πš‚π™°π™Όπ™΄ measures the πšπš’πšœπšπšŠπš—πšŒπšŽ of the current solution from the previous solution. This corresponds to the number of variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 that are assigned to the same previous value.

See also

root concept: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

Keywords

characteristic of a constraint: sort based reformulation, automaton, automaton with array of counters.

constraint type: proximity constraint.

modelling: functional dependency.

Cond. implications

πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšœπšŠπš–πšŽ_πšŸπšŠπš•πšžπšŽ(π™½πš‚π™°π™Όπ™΄,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2)

Β Β Β  withΒ  2*π™½πš‚π™°π™Όπ™΄=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|

Β Β implies πšπš’πšπšπšŽπš›_πšπš›πš˜πš–_πšŽπš‘πšŠπšŒπšπš•πš’_πš”_πš™πš˜πšœ(𝙺,πš…π™΄π™²πšƒπ™Ύπš1,πš…π™΄π™²πšƒπ™Ύπš2).

Arc input(s)

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

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡(πΆπΏπΌπ‘„π‘ˆπΈ,𝐿𝑂𝑂𝑃,=)β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
β€’ πŒπ€π—_𝐍𝐒𝐂𝐂≀1
β€’ 𝐍𝐀𝐑𝐂_𝐍𝐎_π‹πŽπŽπ=π™½πš‚π™°π™Όπ™΄

Graph model

The arc generator π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡(πΆπΏπΌπ‘„π‘ˆπΈ,𝐿𝑂𝑂𝑃,=) is used in order to generate all the arcs of the initial graph:

  • The arc generator πΆπΏπΌπ‘„π‘ˆπΈ creates all links between the items of the first collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,

  • The arc generator 𝐿𝑂𝑂𝑃 creates a loop for each item of the second collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,

  • Finally the arc generator π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡(=) creates an arc between items located at the same position in the collections πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.

PartΒ (A) of FigureΒ 5.21.1 gives the initial graph associated with the Example slot. Variables of collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 are coloured, while variables of collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 are kept in white. PartΒ (B) represents the final graph associated with the Example slot. In this graph each vertex constitutes a strongly connected component and the number of arcs that do not correspond to a loop is equal to 2 (i.e.,Β π™½πš‚π™°π™Όπ™΄).

Figure 5.21.1. (A)Β Initial and (B)Β final graph of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšœπšŠπš–πšŽ_πšŸπšŠπš•πšžπšŽ(2,〈U 1 ,U 2 ,U 3 ,U 4 βŒͺ, 〈V 1 ,V 2 ,V 3 ,V 4 βŒͺ) constraint with U 1 =7, U 2 =3, U 3 =1, U 4 =5 and V 1 =1, V 2 =3, V 3 =1, V 4 =7 (in PartΒ (B) arcs in red correspond to the arcs counted by the argument π™½πš‚π™°π™Όπ™΄)
ctrs/alldifferent_same_value-1-tikz
Automaton

FigureΒ 5.21.2 depicts the automaton associated with the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšœπšŠπš–πšŽ_πšŸπšŠπš•πšžπšŽ constraint. Let πš…π™°πš1 i and πš…π™°πš2 i respectively denote the i th variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collections. To each pair of variables (πš…π™°πš1 i ,πš…π™°πš2 i ) corresponds a signature variable πš‚ i . The following signature constraint links πš…π™°πš1 i , πš…π™°πš2 i and πš‚ i : πš…π™°πš1 i =πš…π™°πš2 i β‡”πš‚ i .

Figure 5.21.2. Automaton of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšœπšŠπš–πšŽ_πšŸπšŠπš•πšžπšŽ constraint
ctrs/alldifferent_same_value-2-tikz