5.372. sort_permutation
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Usual name
- Synonyms
, , , .
- Arguments
- Restrictions
- Purpose
The variables of collection correspond to the variables of collection according to the permutation (i.e.,Β ). The variables of collection are also sorted in increasing order.
- Example
-
The constraint holds since:
-
The first item of collection corresponds to the item of collection .
The second item of collection corresponds to the item of collection .
The third item of collection corresponds to the item of collection .
The fourth item of collection corresponds to the item of collection .
The fifth item of collection corresponds to the item of collection .
The sixth item of collection corresponds to the item of collection .
The items of collection are sorted in increasing order.
Figure 5.372.1. Illustration of the correspondence between the items of the and the collections according to the permutation defined by the items of the collection of the Example slot (note that the items of the collection are sorted in increasing order)
-
- Typical
- Symmetry
One and the same constant can be added to the attributes of all items of and .
- Arg. properties
Functional dependency: determined by .
Functional dependency: determined by and .
- Remark
This constraint is referenced under the name in SICStus Prolog.
- Algorithm
- Reformulation
Let denote the number of variables in the collection . The constraint can be reformulated as a conjunction of the form:
Β Β Β
To enhance the previous model, the following necessary condition was proposed by P.Β Schaus. (i.e.,Β at most variables of the collection are assigned a value strictly less than ). Similarly, we have that (i.e.,Β at most variables of the collection are assigned a value are strictly greater than ).
- Systems
- See also
common keyword: Β (sort, permutation).
implies: .
specialisation: Β ( parameter removed).
used in reformulation: , , .
- 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
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
PartsΒ (A) andΒ (B) of FigureΒ 5.372.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 arcs: all the inequalities constraints between consecutive variables of holds.
Figure 5.372.2. Initial and final graph of the constraint
(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 . Therefore we can rewrite to and simplify to .