5.98. derangement

Origin
Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }\right)$

Argument
 $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi ‘}-\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$
Restrictions
 $|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|>1$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi },\left[\mathrm{\pi \pi \pi \pi \pi ‘},\mathrm{\pi \pi \pi \pi }\right]\right)$ $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }.\mathrm{\pi \pi \pi \pi \pi ‘}\beta ₯1$ $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }.\mathrm{\pi \pi \pi \pi \pi ‘}\beta €|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi },\mathrm{\pi \pi \pi \pi \pi ‘}\right)$ $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }.\mathrm{\pi \pi \pi \pi }\beta ₯1$ $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }.\mathrm{\pi \pi \pi \pi }\beta €|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|$
Purpose

Enforce to have a permutation with no cycle of length one. The permutation is depicted by the $\mathrm{\pi \pi \pi \pi }$ attribute of the $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ collection.

Example
$\left(\begin{array}{c}β©\begin{array}{cc}\mathrm{\pi \pi \pi \pi \pi ‘}-1\hfill & \mathrm{\pi \pi \pi \pi }-2,\hfill \\ \mathrm{\pi \pi \pi \pi \pi ‘}-2\hfill & \mathrm{\pi \pi \pi \pi }-1,\hfill \\ \mathrm{\pi \pi \pi \pi \pi ‘}-3\hfill & \mathrm{\pi \pi \pi \pi }-5,\hfill \\ \mathrm{\pi \pi \pi \pi \pi ‘}-4\hfill & \mathrm{\pi \pi \pi \pi }-3,\hfill \\ \mathrm{\pi \pi \pi \pi \pi ‘}-5\hfill & \mathrm{\pi \pi \pi \pi }-4\hfill \end{array}βͺ\hfill \end{array}\right)$

In the permutation of the example we have the following 2 cycles: $1\beta 2\beta 1$ and $3\beta 5\beta 4\beta 3$. Since these cycles have both a length strictly greater than one the corresponding $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint holds.

Typical
$|\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }|>2$
Symmetries
• Items of $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ are permutable.

• Attributes of $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ are permutable w.r.t. permutation $\left(\mathrm{\pi \pi \pi \pi \pi ‘},\mathrm{\pi \pi \pi \pi }\right)$ (permutation applied to all items).

Remark

A special case of the $\mathrm{\pi \pi ’\pi \pi \pi }$ [BeldiceanuContejean94] constraint.

Keywords
Arc input(s)

$\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$

Arc generator
$\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arity
Arc constraint(s)
 $\beta ’\mathrm{\pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi \pi }=\mathrm{\pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi \pi \pi ‘}$
Graph property(ies)
$\mathrm{\pi \pi \pi \pi \pi }$$=0$

Graph class
$\mathrm{\pi Ύ\pi ½\pi ΄}_\mathrm{\pi \pi \pi ²\pi ²}$

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.98.1 respectively show the initial and final graph associated with the Example slot. The $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint holds since the final graph does not contain any vertex that does not belong to a circuit (i.e.,Β $\mathrm{\pi \pi \pi \pi \pi }$ $=$ 0).

In order to express the binary constraint that links two vertices of the $\mathrm{\pi ½\pi Ύ\pi ³\pi ΄\pi }$ collection one has to make explicit the index value of the vertices. This is why the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint considers objects that have two attributes:

• One fixed attribute $\mathrm{\pi \pi \pi \pi \pi ‘}$ that is the identifier of the vertex,

• One variable attribute $\mathrm{\pi \pi \pi \pi }$ 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 $\mathrm{\pi \pi \pi \pi \pi }$ we can rewrite the graph property $\mathrm{\pi \pi \pi \pi \pi }$ $=$ 0 to $\mathrm{\pi \pi \pi \pi \pi }$ $\beta €$ 0. This leads to simplify $\underset{Μ²}{\stackrel{Β―}{\mathrm{\pi \pi \pi \pi \pi }}}$ to $\underset{Μ²}{\mathrm{\pi \pi \pi \pi \pi }}$.