5.308. sort_permutation

Origin

[Zhou97]

Constraint

sort_permutation​(FROM,​PERMUTATION,​TO)​

Usual name

sort

Synonym(s)

extended_sortedness, sorted, sorting.

Argument(s)

FROM	collection​(var−dvar)​
PERMUTATION	collection​(var−dvar)​
TO	collection​(var−dvar)​

Restriction(s)

|PERMUTATION|=|FROM|

|PERMUTATION|=|TO|

PERMUTATION.var≥1

PERMUTATION.var≤|PERMUTATION|

alldifferent​(PERMUTATION)​

required​(FROM,​var)​

required​(PERMUTATION,​var)​

required​(TO,​var)​

Purpose

The variables of collection FROM correspond to the variables of collection TO according to the permutation PERMUTATION (i.e., FROM​[i]​.var=TO​[PERMUTATION​[i]​.var]​.var). The variables of collection TO 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 sort_permutation constraint holds since:

• • The first item FROM​[1]​.var=1 of collection FROM corresponds to the PERMUTATION​[1]​.var=1^th item of collection TO.

  • The second item FROM​[2]​.var=9 of collection FROM corresponds to the PERMUTATION​[2]​.var=6^th item of collection TO.

  • The third item FROM​[3]​.var=1 of collection FROM corresponds to the PERMUTATION​[3]​.var=3^th item of collection TO.

  • The fourth item FROM​[4]​.var=5 of collection FROM corresponds to the PERMUTATION​[4]​.var=5^th item of collection TO.

  • The fifth item FROM​[5]​.var=2 of collection FROM corresponds to the PERMUTATION​[5]​.var=4^th item of collection TO.

  • The sixth item FROM​[6]​.var=1 of collection FROM corresponds to the PERMUTATION​[6]​.var=2^th item of collection TO.

• The items of collection TO=〈1,​1,​1,​2,​5,​9〉 are sorted in increasing order.

Figure 5.308.1. Illustration of the correspondence between the items of the FROM and the TO collections according to the permutation defined by the items of the PERMUTATION collection

Remark

This constraint is referenced under the name sorting in SICStus Prolog.

Algorithm

[Zhou97].

Systems

sorted in Gecode, sorting in SICStus.

See also

correspondence, sort.

Key words

characteristic of a constraint: sort, derived collection.

combinatorial object: permutation.

constraint arguments: constraint between three collections of variables.

Derived Collection(s)

col( FROM_PERMUTATION−collection​(var−dvar,​ind−dvar)​,​ item​(var−FROM.var,​ind−PERMUTATION.var)​]​ )

---

Arc input(s)

FROM_PERMUTATION TO

Arc generator

PRODUCT↦collection​(from_permutation,​to)​

Arc arity

2

Arc constraint(s)

• from_permutation.var=to.var

• from_permutation.ind=to.key

Graph property(ies)

NARC=|PERMUTATION|

---

Arc input(s)

TO

Arc generator

PATH↦collection​(to1,​to2)​

Arc arity

2

Arc constraint(s)

to1.var≤to2.var

Graph property(ies)

NARC=|TO|−1

---

Graph model

Parts (A) and (B) of Figure 5.308.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 FROM_PERMUTATION, while the sink vertices correspond to the items of the TO collection. Since the first graph constraint uses the NARC graph property, the arcs of its final graph are stressed in bold. The sort_permutation constraint holds since:

• The first graph constraint holds since its final graph contains exactly PERMUTATION arcs.

• Finally the second graph constraint holds also since its corresponding final graph contains exactly |PERMUTATION−1| arcs: all the inequalities constraints between consecutive variables of TO holds.

Figure 5.308.2. Initial and final graph of the sort_permutation constraint

(a)	(b)

Signature

Consider the first graph constraint where we use the PRODUCT arc generator. Since all the key attributes of the TO collection are distinct, and because of the second condition from_permutation.ind=to.key 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 |PERMUTATION|. So we can rewrite the graph property NARC=|PERMUTATION| to NARC≥|PERMUTATION| and simplify NARC to NARC.

Consider now the second graph constraint. Since we use the PATH arc generator with an arity of 2 on the TO collection, the maximum number of arcs of the corresponding final graph is equal to |TO|−1. Therefore we can rewrite NARC=|TO|−1 to NARC≥|TO|−1 and simplify NARC to NARC.