5.19. alldifferent_on_intersection
| DESCRIPTION | LINKS | GRAPH | AUTOMATON |
- Origin
- Constraint
- Synonyms
, .
- Arguments
- Restrictions
- Purpose
The values that both occur in the and collections have only one occurrence.
- Example
-
The constraint holds since the values 9 and 1 that both occur in as well as in have exactly one occurrence in each collection.
- Typical
- 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.
- Arg. properties
Contractible wrt. .
Contractible wrt. .
- See also
common keyword: , Β (constraint on the intersection).
implies: .
- 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)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph class
-
- Graph model
PartsΒ (A) andΒ (B) of FigureΒ 5.19.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 components 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.19.1. Initial and final graph of the constraint
(a) (b)
- Automaton
FigureΒ 5.19.2 depicts the automaton associated with the constraint. To each variable of the collection corresponds a signature variable that is equal to 0. To each variable of the collection corresponds a signature variable that is equal to 1. The automaton first counts the number of occurrences of each value assigned to the variables of the collection. It then counts the number of occurrences of each value assigned to the variables of the collection. Finally, the automaton imposes that each value is not taken by two variables of both collections.
Figure 5.19.2. Automaton of the constraint
