5.339. same_modulo
DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Arguments
- Restrictions
- Purpose
For each integer in , let (respectively ) denote the number of variables of (respectively ) that have as a rest when divided by . For all in we have that .
- Example
-
The values of the first collection are respectively associated with the equivalence classes , , , , , . Therefore the equivalence classes 0, 1, and 2 are respectively used 1, 3, and 2 times. Similarly, the values of the second collection are respectively associated with the equivalence classes , , , , , . Therefore the equivalence classes 0, 1, and 2 are respectively used 1, 3, and 2 times. Consequently the constraint holds. FigureΒ 5.339.1 illustrates this correspondence.
Figure 5.339.1. Illustration of the correspondence between the items of the and of the collections of the Example slot
- Typical
- Symmetries
Arguments are permutable w.r.t. permutation .
Items of are permutable.
Items of are permutable.
An occurrence of a value of can be replaced by any other value such that is congruent to modulo .
- Arg. properties
Aggregate: , , .
- Used in
- See also
implies: .
soft variant: Β (variable-based violation measure).
specialisation: Β ( replaced by ).
- Keywords
characteristic of a constraint: sort based reformulation, modulo.
combinatorial object: permutation.
constraint arguments: constraint between two collections of variables.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
PartsΒ (A) andΒ (B) of FigureΒ 5.339.2 respectively show the initial and final graph associated with the Example slot. Since we use the and graph properties, the source and sink vertices of the final graph are stressed with a double circle. Since there is a constraint on each connected component of the final graph we also show the different connected components. Each of them corresponds to an equivalence class according to the arc constraint. The constraint holds since:
Each connected component of the final graph has the same number of sources and of sinks.
The number of sources of the final graph is equal to .
The number of sinks of the final graph is equal to .
Figure 5.339.2. Initial and final graph of the constraint
(a) (b) - Signature
Since the initial graph contains only sources and sinks, and since isolated vertices are eliminated from the final graph, we make the following observations:
Sources of the initial graph cannot become sinks of the final graph,
Sinks of the initial graph cannot become sources of the final graph.
From the previous observations and since we use the arc generator on the collections and , we have that the maximum number of sources and sinks of the final graph is respectively equal to and . Therefore we can rewrite to and simplify to . In a similar way, we can rewrite to and simplify to .