[OlderSwinkelsEmden95]

$\mathrm{𝚜𝚘𝚛𝚝}(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2})$

$\mathrm{𝚜𝚘𝚛𝚝𝚎𝚍𝚗𝚎𝚜𝚜}$, $\mathrm{𝚜𝚘𝚛𝚝𝚎𝚍}$, $\mathrm{𝚜𝚘𝚛𝚝𝚒𝚗𝚐}$.

The $\mathrm{𝚜𝚘𝚛𝚝}$ constraint holds since:

• Values 1, 2, 5 and 9 have the same number of occurrences within both collections $\langle 1,9,1,5,2,1\rangle$ and $\langle 1,1,1,2,5,9\rangle$. Figure 5.313.1 illustrates this correspondence.

• The items of collection $\langle 1,1,1,2,5,9\rangle$ are sorted in increasing order.

Figure 5.313.1. Correspondence between collection $\langle 1,9,1,5,2,1\rangle$ and collection $\langle 1,1,1,2,5,9\rangle$

• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$ are permutable.

• One and the same constant can be added to the $\mathrm{𝚟𝚊𝚛}$ attributes of all items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$ and $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$.

A variant of this constraint was introduced in [Zhou97]. In this variant an additional list of domain variables represents the permutation that allows to go from $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$ to $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$.

[GuernalecColmerauer97], [MehlhornThiel00].

sorting in Choco, sorted in Gecode, sorting in SICStus.

generalisation: $\mathrm{𝚜𝚘𝚛𝚝}\_\mathrm{𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗}$ ($\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}$ parameter added).

implies: $\mathrm{𝚜𝚊𝚖𝚎}$.

characteristic of a constraint: sort.

combinatorial object: permutation.

constraint arguments: constraint between two collections of variables.

filtering: bound-consistency.

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$

Parts (A) and (B) of Figure 5.313.2 respectively show the initial and final graph associated with the first graph constraint of the Example slot. Since it uses the $\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}$ and $\mathrm{𝐍𝐒𝐈𝐍𝐊}$ graph properties, the source and sink vertices of this final graph are stressed with a double circle. Since there is a constraint on each connected component of the final graph we also show the different connected components. The $\mathrm{𝚜𝚘𝚛𝚝}$ constraint holds since:

• Each connected component of the final graph of the first graph constraint has the same number of sources and of sinks.

• The number of sources of the final graph of the first graph constraint is equal to $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}\right|$.

• The number of sinks of the final graph of the first graph constraint is equal to $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}\right|$.

• Finally the second graph constraint holds also since its corresponding final graph contains exactly $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}-1|$ arcs: all the inequalities constraints between consecutive variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$ holds.

Figure 5.313.2. Initial and final graph of the $\mathrm{𝚜𝚘𝚛𝚝}$ constraint

(a)

(b)

Consider the first graph constraint. Since the initial graph contains only sources and sinks, and since isolated vertices are eliminated from the final graph, we make the following observations:

• Sources of the initial graph cannot become sinks of the final graph,

• Sinks of the initial graph cannot become sources of the final graph.

From the previous observations and since we use the $\mathrm{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}$ arc generator on the collections $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$ and $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$, we have that the maximum number of sources and sinks of the final graph is respectively equal to $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}\right|$ and $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}\right|$. Therefore we can rewrite $\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}=\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}\right|$ to $\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}\ge \left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}\right|$ and simplify $\underline{\overline{\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}}}$ to $\overline{\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}}$. In a similar way, we can rewrite $\mathrm{𝐍𝐒𝐈𝐍𝐊}=\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}\right|$ to $\mathrm{𝐍𝐒𝐈𝐍𝐊}\ge \left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}\right|$ and simplify $\underline{\overline{\mathrm{𝐍𝐒𝐈𝐍𝐊}}}$ to $\overline{\mathrm{𝐍𝐒𝐈𝐍𝐊}}$.

Consider now the second graph constraint. Since we use the $\mathrm{𝑃𝐴𝑇𝐻}$ arc generator with an arity of 2 on the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$ collection, the maximum number of arcs of the final graph is equal to $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}\right|-1$. Therefore we can rewrite the graph property $\mathrm{𝐍𝐀𝐑𝐂}=\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}\right|-1$ to $\mathrm{𝐍𝐀𝐑𝐂}\ge \left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}\right|-1$ and simplify $\underline{\overline{\mathrm{𝐍𝐀𝐑𝐂}}}$ to $\overline{\mathrm{𝐍𝐀𝐑𝐂}}$.