5.12. alldifferent_on_intersection

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

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

Constraint

πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš˜πš—_πš’πš—πšπšŽπš›πšœπšŽπšŒπšπš’πš˜πš—(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2)

Synonyms

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

Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,πšŸπšŠπš›)
Purpose

The values that both occur in the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collections have only one occurrence.

Example
5,9,1,5,πšŸπšŠπš›-2,πšŸπšŠπš›-1,πšŸπšŠπš›-6,πšŸπšŠπš›-9,πšŸπšŠπš›-6,πšŸπšŠπš›-2

The πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš˜πš—_πš’πš—πšπšŽπš›πšœπšŽπšŒπšπš’πš˜πš— constraint holds since the values 9 and 1 that both occur in 〈5,9,1,5βŒͺ as well as in 〈2,1,6,9,6,2βŒͺ have exactly one occurrence in each collection.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|>1
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|>1
Symmetries
  • Arguments are permutable w.r.t. permutation (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2).

  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 are permutable.

  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 are permutable.

  • 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.

See also

common keyword: πšŒπš˜πš–πš–πš˜πš—, πš—πšŸπšŠπš•πšžπšŽ_πš˜πš—_πš’πš—πšπšŽπš›πšœπšŽπšŒπšπš’πš˜πš—Β (constraint on the intersection).

implied by: πšπš’πšœπš“πš˜πš’πš—πš.

implies: πšœπšŠπš–πšŽ_πš’πš—πšπšŽπš›πšœπšŽπšŒπšπš’πš˜πš—.

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

Keywords

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

constraint arguments: constraint between two collections of variables.

constraint type: constraint on the intersection, value constraint.

final graph structure: connected component, acyclic, bipartite, no loop.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
πŒπ€π—_𝐍𝐂𝐂≀2

Graph class
β€’ π™°π™²πšˆπ™²π™»π™Έπ™²
β€’ π™±π™Έπ™Ώπ™°πšπšƒπ™Έπšƒπ™΄
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.12.1 respectively show the initial and final graph associated with the Example slot. Since we use the πŒπ€π—_𝐍𝐂𝐂 graph property we show one of the largest connected component of the final graph. The πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš˜πš—_πš’πš—πšπšŽπš›πšœπšŽπšŒπšπš’πš˜πš— constraint holds since each connected component has at most two vertices. Note that all the vertices corresponding to the variables that take values 5, 2 or 6 were removed from the final graph since there is no arc for which the associated equality constraint holds.

Figure 5.12.1. Initial and final graph of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš˜πš—_πš’πš—πšπšŽπš›πšœπšŽπšŒπšπš’πš˜πš— constraint
ctrs/alldifferent_on_intersectionActrs/alldifferent_on_intersectionB
(a) (b)
Automaton

FigureΒ 5.12.2 depicts the automaton associated with the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš˜πš—_πš’πš—πšπšŽπš›πšœπšŽπšŒπšπš’πš˜πš— constraint. To each variable πš…π™°πš1 i of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 corresponds a signature variable πš‚ i that is equal to 0. To each variable πš…π™°πš2 i of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 corresponds a signature variable πš‚ i+|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| that is equal to 1. The automaton first counts the number of occurrences of each value assigned to the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 collection. It then counts the number of occurrences of each value assigned to the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collection. Finally, the automaton imposes that each value is not taken by two variables of both collections.

Figure 5.12.2. Automaton of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš˜πš—_πš’πš—πšπšŽπš›πšœπšŽπšŒπšπš’πš˜πš— constraint
ctrs/alldifferent_on_intersection1