5.317. pattern
| DESCRIPTION | LINKS | AUTOMATON |
- Origin
- Constraint
- Type
- Arguments
- Restrictions
- Purpose
We quote the definition from the original articleΒ [BourdaisGalinierPesant03] introducing the constraint:
βWe call a -pattern any sequence of elements such that no two successive elements have the same value. Consider a set and a sequence of elements of . In this context, a stretch is a maximum subsequence of variables of which all have the same value. Consider now the sequence of the types of the successive stretches that appear in . Let be a set of -patterns. satisfies if and only if every subsequence of elements in belongs to .β
- Example
-
The constraint holds since, as depicted by FigureΒ 5.317.1, all its sequences of three consecutive stretches correspond to one of the 3-patterns given in the collection.
Figure 5.317.1. The sequence of the Example slot, its four stretches and the corresponding two 3-patterns and
- Typical
- Symmetries
Items of are permutable.
Items of and are simultaneously reversable.
All occurrences of two distinct tuples of values in or can be swapped; all occurrences of a tuple of values in or can be renamed to any unused tuple of values.
- Arg. properties
Prefix-contractible wrt. .
Suffix-contractible wrt. .
- Usage
The constraint was originally introduced within the context of staff scheduling. In this context, the value of the variable of the collection corresponds to the type of shift performed by a person on the day. A stretch is a maximum sequence of consecutive variables that are all assigned to the same value. The constraint imposes that each sequence of consecutive stretches belongs to a given list of patterns.
- Remark
A generalisation of the constraint to the constraint enforcing the fact that a sequence of variables corresponds to a regular expression is presented inΒ [Pesant04].
- See also
common keyword: Β (timetabling constraint),
Β (sliding sequence constraint),
- Keywords
characteristic of a constraint: automaton, automaton without counters, reified automaton constraint.
constraint network structure: Berge-acyclic constraint network.
constraint type: timetabling constraint, sliding sequence constraint.
- Automaton
Taking advantage that all -patterns have the same length , it is straightforward to construct an automaton that only accepts solutions of the constraint. FigureΒ 5.317.2 depicts the automaton associated with the constraint of the Example slot. The construction can be done in three steps:
First, build a prefix tree of all the -patterns. In the context of our example, this gives all arcs of FigureΒ 5.317.2, except self loops and the arc from to .
Second, find out the transitions that exit a leave of the tree. For this purpose we remove the first symbol of the corresponding -pattern, add at the end of the remaining -pattern a symbol corresponding to a stretch value, and check whether the new pattern belongs or not to the set of -patterns of the constraint. When the new pattern belongs to the set of -patterns we add a corresponding transition. For instance, in the context of our example, consider the leave that is associated with the 3-pattern . We remove the first symbol 1 and get . We then try to successively add the stretch values 1, 2 and 3 to the end of and check if the corresponding patterns ,Β Β and belong or not to our set of 3-patterns. Since only is a 3-pattern we add a new transition between the corresponding leaves of the prefix tree (i.e.,Β a transition from to ).
Third, in order to take into account that each value of a -pattern corresponds in fact to a given stretch value (i.e.,Β several consecutive values that are assigned the same value), we add a self loop to all non-source states with a transition label that corresponds to the transition label of their entering arc.
Figure 5.317.2. Automaton of the constraint of the Example slot
