5.114. derangement
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Argument
- Restrictions
- Purpose
Enforce to have a permutation with no cycle of length one. The permutation is depicted by the attribute of the collection.
- Example
-
In the permutation of the example we have the following 2 cycles: and . Since these cycles have both a length strictly greater than one the corresponding constraint holds.
- Typical
- Symmetries
Items of are permutable.
Attributes of are permutable w.r.t. permutation (permutation applied to all items).
- Remark
A special case of the [BeldiceanuContejean94] constraint.
- Counting
-
Length () 2 3 4 5 6 7 8 9 10 Solutions 1 2 9 44 265 1854 14833 133496 1334961 Number of solutions for : domains
- See also
common keyword: , Β (permutation).
implies: .
- Keywords
characteristic of a constraint: sort based reformulation.
combinatorial object: permutation.
constraint type: graph constraint.
- Cond. implications
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
-
- Graph property(ies)
-
- Graph class
-
- Graph model
PartsΒ (A) andΒ (B) of FigureΒ 5.114.1 respectively show the initial and final graph associated with the Example slot. The constraint holds since the final graph does not contain any vertex that does not belong to a circuit (i.e.,Β 0).
Figure 5.114.1. Initial and final graph of the constraint
(a) (b) In order to express the binary constraint that links two vertices of the collection one has to make explicit the index value of the vertices. This is why the constraint considers objects that have two attributes:
One fixed attribute that is the identifier of the vertex,
One variable attribute that is the successor of the vertex.
Forbidding cycles of length one is achieved by the second condition of the arc constraint.
- Signature
Since 0 is the smallest possible value of we can rewrite the graph property 0 to 0. This leads to simplify to .