5.313. sort

DESCRIPTIONLINKSGRAPH
Origin

[OlderSwinkelsEmden95]

Constraint

πšœπš˜πš›πš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2)

Synonyms

πšœπš˜πš›πšπšŽπšπš—πšŽπšœπšœ, πšœπš˜πš›πšπšŽπš, πšœπš˜πš›πšπš’πš—πš.

Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,πšŸπšŠπš›)
Purpose

The variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 correspond to the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 according to a permutation. The variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 are also sorted in increasing order.

Example
πšŸπšŠπš›-1,πšŸπšŠπš›-9,πšŸπšŠπš›-1,πšŸπšŠπš›-5,πšŸπšŠπš›-2,πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-2,πšŸπšŠπš›-5,πšŸπšŠπš›-9

The πšœπš˜πš›πš 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.313.1 illustrates this correspondence.

  • The items of collection 〈1,1,1,2,5,9βŒͺ are sorted in increasing order.

Figure 5.313.1. Correspondence between collection 〈1,9,1,5,2,1βŒͺ and collection 〈1,1,1,2,5,9βŒͺ
ctrs/sort1
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 are permutable.

  • One and the same constant can be added to the πšŸπšŠπš› attributes of all items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.

Remark

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 πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 to πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.

Algorithm

[GuernalecColmerauer97], [MehlhornThiel00].

Systems

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

See also

generalisation: πšœπš˜πš›πš_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš—Β (π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½ parameter added).

implies: πšœπšŠπš–πšŽ.

Keywords

characteristic of a constraint: sort.

combinatorial object: permutation.

constraint arguments: constraint between two collections of variables.

filtering: bound-consistency.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
β€’ for all connected components: ππ’πŽπ”π‘π‚π„=ππ’πˆππŠ
β€’ ππ’πŽπ”π‘π‚π„=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|
β€’ ππ’πˆππŠ=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›β‰€πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|-1

Graph model

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 ππ’πŽπ”π‘π‚π„ and ππ’πˆππŠ 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 πšœπš˜πš›πš 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 |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|.

  • The number of sinks of the final graph of the first graph constraint is equal to |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|.

  • Finally the second graph constraint holds also since its corresponding final graph contains exactly |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1-1| arcs: all the inequalities constraints between consecutive variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 holds.

Figure 5.313.2. Initial and final graph of the πšœπš˜πš›πš constraint
ctrs/sortA
(a)
ctrs/sortB
(b)
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 π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡ arc generator on the collections πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2, we have that the maximum number of sources and sinks of the final graph is respectively equal to |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| and |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|. Therefore we can rewrite ππ’πŽπ”π‘π‚π„=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| to ππ’πŽπ”π‘π‚π„β‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| and simplify ππ’πŽπ”π‘π‚π„ Β― Μ² to ππ’πŽπ”π‘π‚π„ Β―. In a similar way, we can rewrite ππ’πˆππŠ=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2| to ππ’πˆππŠβ‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2| and simplify ππ’πˆππŠ Β― Μ² to ππ’πˆππŠ Β―.

Consider now the second graph constraint. Since we use the 𝑃𝐴𝑇𝐻 arc generator with an arity of 2 on the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collection, the maximum number of arcs of the final graph is equal to |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|-1. Therefore we can rewrite the graph property 𝐍𝐀𝐑𝐂=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|-1 to 𝐍𝐀𝐑𝐂β‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|-1 and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.