5.46. balance_modulo
DESCRIPTION | LINKS | GRAPH | AUTOMATON |
- Origin
- Constraint
- Arguments
- Restrictions
- Purpose
Consider the largest set (respectively the smallest set ) of variables of the collection that have the same remainder when divided by . is equal to the difference between the cardinality of and the cardinality of .
- Example
-
In this example values 6, 1, 7, 1, 5 are respectively associated with the equivalence classes , , , , . Therefore the equivalence classes 0, 1 and 2 are respectively used 1, 3 and 1 times. The constraint holds since its first argument is assigned to the difference between the maximum and minimum number of the previous occurrences (i.e.,ย ).
- Typical
- Symmetries
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
Functional dependency: determined by and .
- Usage
An application of the constraint is to enforce a balanced assignment of values, no matter how many distinct equivalence classes will be used. In this case one will push down the maximum value of the first argument of the constraint.
- See also
specialisation: ย ( replaced by ).
- Keywords
-
characteristic of a constraint: modulo, automaton, automaton with array of counters.
constraint arguments: pure functional dependency.
constraint type: value constraint.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph class
-
- Graph model
The graph property constraints the difference between the sizes of the largest and smallest strongly connected components.
Partsย (A) andย (B) of Figureย 5.46.1 respectively show the initial and final graph associated with the Example slot. Since we use the graph property, we show the largest and smallest strongly connected components of the final graph.
Figure 5.46.1. Initial and final graph of the constraint
(a) (b)
- Automaton
Figureย 5.46.2 depicts the automaton associated with the constraint. To each item of the collection corresponds a signature variable that is equal to 1.
Figure 5.46.2. Automaton of the constraint