5.14. 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 3 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.

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 of 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 not assigned to the same previous value.

See also

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

Keywords

characteristic of a constraint: automaton, automaton with array of counters.

constraint type: proximity constraint.

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.14.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.14.1. Initial and final graph of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšœπšŠπš–πšŽ_πšŸπšŠπš•πšžπšŽ constraint
ctrs/alldifferent_same_value1
Automaton

FigureΒ 5.14.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.14.2. Automaton of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšœπšŠπš–πšŽ_πšŸπšŠπš•πšžπšŽ constraint
ctrs/alldifferent_same_value2