5.36. balance
| DESCRIPTION | LINKS | GRAPH | AUTOMATON |
- Origin
N.Β Beldiceanu
- Constraint
- Arguments
- Restrictions
- Purpose
is equal to the difference between the number of occurrence of the value that occurs the most and the value that occurs the least within the collection of variables .
- Example
-
In this example, values and 7 are respectively used 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.,Β ). FigureΒ 5.36.1 shows the solution associated with the example.
Figure 5.36.1. Illustration of the example: five variables respectively fixed to values 3, 1, 7, 1 and 1, and the corresponding value of
- Typical
- Symmetries
Items of are permutable.
All occurrences of two distinct values of can be swapped; all occurrences of a value of can be renamed to any unused value.
- Usage
An application of the constraint is to enforce a balanced assignment of values, no matter how many distinct values will be used. In this case one will push down the maximum value of the first argument of the constraint.
- Remark
If we do not want to use an automaton with an array of counters a possible reformulation of the constraint can be achieved in the following way. We use a constraint in order to reorder the variables of the collection and compute the difference between the longest and the smallest sequences of consecutive values.
- See also
generalisation: Β ( replaced by ), Β ( replaced by ), Β ( replaced by ).
related: Β (balanced assignment versus balanced tree).
- Keywords
-
characteristic of a constraint: automaton, automaton with array of counters.
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.36.2 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.36.2. Initial and final graph of the constraint
(a) (b)
- Automaton
FigureΒ 5.36.3 depicts the automaton associated with the constraint. To each item of the collection corresponds a signature variable that is equal to 1.
Figure 5.36.3. Automaton of the constraint
