## 5.371. sort

Origin
Constraint

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

Synonyms

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

Arguments
 $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}|=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1},\mathrm{𝚟𝚊𝚛}\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2},\mathrm{𝚟𝚊𝚛}\right)$
Purpose

First, the variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$ correspond to a permutation of the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$. Second, the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$ are sorted in increasing order.

Example
$\left(〈1,9,1,5,2,1〉,〈1,1,1,2,5,9〉\right)$

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

• Values 1, 2, 5 and 9 have the same number of occurrences within both collections $〈1,9,1,5,2,1〉$ and $〈1,1,1,2,5,9〉$. Figure 5.371.1 illustrates this correspondence.

• The items of collection $〈1,1,1,2,5,9〉$ are sorted in increasing order.

All solutions

Figure 5.371.2 gives all solutions to the following non ground instance of the $\mathrm{𝚜𝚘𝚛𝚝}$ constraint: ${V}_{1}\in \left[2,3\right]$, ${V}_{2}\in \left[2,3\right]$, ${V}_{3}\in \left[1,2\right]$, ${V}_{4}\in \left[4,5\right]$, ${V}_{5}\in \left[2,4\right]$, ${S}_{1}\in \left[2,3\right]$, ${S}_{2}\in \left[2,3\right]$, ${S}_{3}\in \left[1,3\right]$, ${S}_{4}\in \left[4,5\right]$, ${S}_{5}\in \left[2,5\right]$, $\mathrm{𝚜𝚘𝚛𝚝}$$\left(〈{V}_{1},{V}_{2},{V}_{3},{V}_{4},{V}_{5}〉,〈{S}_{1},{S}_{2},{S}_{3},{S}_{4},{S}_{5}〉\right)$.

Typical
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}|>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}.\mathrm{𝚟𝚊𝚛}\right)>1$
Symmetries
• 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}$.

Arg. properties

Functional dependency: $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$ determined by $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$.

Usage

The main usage of the $\mathrm{𝚜𝚘𝚛𝚝}$ constraint, that was not foreseen when the $\mathrm{𝚜𝚘𝚛𝚝}$ constraint was invented, is its use in many reformulations. Many constraints involving one or several collections of variables become much simpler to express when the variables of these collections are sorted. In addition these reformulations typically have a size that is linear in the number of variables of the original constraint. This justifies why the $\mathrm{𝚜𝚘𝚛𝚝}$ constraint is considered to be a core constraint. As illustrative examples of these types of reformulations we successively consider the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ and the $\mathrm{𝚜𝚊𝚖𝚎}$ constraints:

Remark

A variant of this constraint called $\mathrm{𝚜𝚘𝚛𝚝}_\mathrm{𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗}$ 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}$.

Algorithm
Systems

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

Keywords
Arc input(s)

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

Arc generator
$\mathrm{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}=\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚟𝚊𝚛}$
Graph property(ies)
 $•\text{for}\text{all}\text{connected}\text{components:}$$\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}$$=$$\mathrm{𝐍𝐒𝐈𝐍𝐊}$ $•$$\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}$$=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}|$ $•$$\mathrm{𝐍𝐒𝐈𝐍𝐊}$$=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|$

Arc input(s)

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

Arc generator
$\mathrm{𝑃𝐴𝑇𝐻}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}\le \mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚟𝚊𝚛}$
Graph property(ies)
$\mathrm{𝐍𝐀𝐑𝐂}$$=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|-1$

Graph model

Parts (A) and (B) of Figure 5.371.3 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 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}|$.

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

• 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.

Signature

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 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}|$ and $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|$. Therefore we can rewrite $\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}|$ to $\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}\ge |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}|$ and simplify $\underline{\overline{\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}}}$ to $\overline{\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}}$. In a similar way, we can rewrite $\mathrm{𝐍𝐒𝐈𝐍𝐊}=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|$ to $\mathrm{𝐍𝐒𝐈𝐍𝐊}\ge |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|$ 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 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|-1$. Therefore we can rewrite the graph property $\mathrm{𝐍𝐀𝐑𝐂}=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|-1$ to $\mathrm{𝐍𝐀𝐑𝐂}\ge |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|-1$ and simplify $\underline{\overline{\mathrm{𝐍𝐀𝐑𝐂}}}$ to $\overline{\mathrm{𝐍𝐀𝐑𝐂}}$.

Quiz

$\mathrm{𝚜𝚘𝚛𝚝}$: checking whether a ground instance holds or not

$\mathrm{𝚜𝚘𝚛𝚝}$: finding all solutions