5.314. sort_permutation

DESCRIPTIONLINKSGRAPH
Origin

[Zhou97]

Constraint

πšœπš˜πš›πš_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš—(π™΅πšπ™Ύπ™Ό,π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½,πšƒπ™Ύ)

Usual name

πšœπš˜πš›πš

Synonyms

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

Arguments
π™΅πšπ™Ύπ™ΌπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πšƒπ™ΎπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
|π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½|=|π™΅πšπ™Ύπ™Ό|
|π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½|=|πšƒπ™Ύ|
π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½.πšŸπšŠπš›β‰₯1
π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½.πšŸπšŠπš›β‰€|π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½|
πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½)
πš›πšŽπššπšžπš’πš›πšŽπš(π™΅πšπ™Ύπ™Ό,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπ™Ύ,πšŸπšŠπš›)
Purpose

The variables of collection π™΅πšπ™Ύπ™Ό correspond to the variables of collection πšƒπ™Ύ according to the permutation π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½ (i.e.,Β π™΅πšπ™Ύπ™Ό[i].πšŸπšŠπš›=πšƒπ™Ύ[π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½[i].πšŸπšŠπš›].πšŸπšŠπš›). The variables of collection πšƒπ™Ύ are also sorted in increasing order.

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

The πšœπš˜πš›πš_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš— constraint holds since:

    • The first item π™΅πšπ™Ύπ™Ό[1].πšŸπšŠπš›=1 of collection π™΅πšπ™Ύπ™Ό corresponds to the π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½[1].πšŸπšŠπš›=1 th item of collection πšƒπ™Ύ.

    • The second item π™΅πšπ™Ύπ™Ό[2].πšŸπšŠπš›=9 of collection π™΅πšπ™Ύπ™Ό corresponds to the π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½[2].πšŸπšŠπš›=6 th item of collection πšƒπ™Ύ.

    • The third item π™΅πšπ™Ύπ™Ό[3].πšŸπšŠπš›=1 of collection π™΅πšπ™Ύπ™Ό corresponds to the π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½[3].πšŸπšŠπš›=3 th item of collection πšƒπ™Ύ.

    • The fourth item π™΅πšπ™Ύπ™Ό[4].πšŸπšŠπš›=5 of collection π™΅πšπ™Ύπ™Ό corresponds to the π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½[4].πšŸπšŠπš›=5 th item of collection πšƒπ™Ύ.

    • The fifth item π™΅πšπ™Ύπ™Ό[5].πšŸπšŠπš›=2 of collection π™΅πšπ™Ύπ™Ό corresponds to the π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½[5].πšŸπšŠπš›=4 th item of collection πšƒπ™Ύ.

    • The sixth item π™΅πšπ™Ύπ™Ό[6].πšŸπšŠπš›=1 of collection π™΅πšπ™Ύπ™Ό corresponds to the π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½[6].πšŸπšŠπš›=2 th item of collection πšƒπ™Ύ.

  • The items of collection πšƒπ™Ύ=〈1,1,1,2,5,9βŒͺ are sorted in increasing order.

Figure 5.314.1. Illustration of the correspondence between the items of the π™΅πšπ™Ύπ™Ό and the πšƒπ™Ύ collections according to the permutation defined by the items of the π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½ collection
ctrs/sort_permutation1
Symmetry

One and the same constant can be added to the πšŸπšŠπš› attributes of all items of π™΅πšπ™Ύπ™Ό and πšƒπ™Ύ.

Remark

This constraint is referenced under the name πšœπš˜πš›πšπš’πš—πš in SICStus Prolog.

Algorithm

[Zhou97].

Systems

sorted in Gecode, sorting in SICStus.

See also

implies: πšŒπš˜πš›πš›πšŽπšœπš™πš˜πš—πšπšŽπš—πšŒπšŽ.

specialisation: πšœπš˜πš›πšΒ (π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½ parameter removed).

Keywords

characteristic of a constraint: sort, derived collection.

combinatorial object: permutation.

constraint arguments: constraint between three collections of variables.

Derived Collection
πšŒπš˜πš•π™΅πšπ™Ύπ™Ό_π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›,πš’πš—πš-πšπšŸπšŠπš›),πš’πšπšŽπš–(πšŸπšŠπš›-π™΅πšπ™Ύπ™Ό.πšŸπšŠπš›,πš’πš—πš-π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½.πšŸπšŠπš›)]
Arc input(s)

π™΅πšπ™Ύπ™Ό_π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½ πšƒπ™Ύ

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπš›πš˜πš–_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš—,𝚝𝚘)

Arc arity
Arc constraint(s)
β€’ πšπš›πš˜πš–_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš—.πšŸπšŠπš›=𝚝𝚘.πšŸπšŠπš›
β€’ πšπš›πš˜πš–_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš—.πš’πš—πš=𝚝𝚘.πš”πšŽπš’
Graph property(ies)
𝐍𝐀𝐑𝐂=|π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½|

Arc input(s)

πšƒπ™Ύ

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚝𝚘1,𝚝𝚘2)

Arc arity
Arc constraint(s)
𝚝𝚘1.πšŸπšŠπš›β‰€πšπš˜2.πšŸπšŠπš›
Graph property(ies)
𝐍𝐀𝐑𝐂=|πšƒπ™Ύ|-1

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.314.2 respectively show the initial and final graph associated with the first graph constraint of the Example slot. In both graphs the source vertices correspond to the items of the derived collection π™΅πšπ™Ύπ™Ό_π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½, while the sink vertices correspond to the items of the πšƒπ™Ύ collection. Since the first graph constraint uses the 𝐍𝐀𝐑𝐂 graph property, the arcs of its final graph are stressed in bold. The πšœπš˜πš›πš_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš— constraint holds since:

  • The first graph constraint holds since its final graph contains exactly π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½ arcs.

  • Finally the second graph constraint holds also since its corresponding final graph contains exactly |π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½-1| arcs: all the inequalities constraints between consecutive variables of πšƒπ™Ύ holds.

Figure 5.314.2. Initial and final graph of the πšœπš˜πš›πš_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš— constraint
ctrs/sort_permutationActrs/sort_permutationB
(a) (b)
Signature

Consider the first graph constraint where we use the π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡ arc generator. Since all the πš”πšŽπš’ attributes of the πšƒπ™Ύ collection are distinct, and because of the second condition πšπš›πš˜πš–_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš—.πš’πš—πš=𝚝𝚘.πš”πšŽπš’ of the arc constraint, each vertex of the final graph has at most one successor. Therefore the maximum number of arcs of the final graph is equal to |π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½|. So we can rewrite the graph property 𝐍𝐀𝐑𝐂=|π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½| to 𝐍𝐀𝐑𝐂β‰₯|π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½| and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.

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