[ library(gfd) | Reference Manual | Alphabetic Index ]
# <ConsistencyModule:> sorted(?Unsorted, ?Sorted, ?Positions)

Sorted is a sorted permutation (described by Positions) of Unsorted
*Unsorted*
- Collection of N (domain) variables or integers
*Sorted*
- Collection of N (domain) variables or integers
*Positions*
- Collection of N (domain) variables or integers

## Description

Declaratively: Sorted is a sorted permutation of Unsorted. Positions
is a collection whose elements range from 1 to N (where N is the
cardinality of the collections) indicating the position of each
unsorted list element within the sorted list. The positions are all
different. The three collections are constrained to have the same size.
Operationally: the elements in all three collections are constrained
such that their domains are consistent with the declarative
meaning.

Two of the three arguments can be uninstantiated or partial lists
at call time.

Any input variables which is not already a domain variable will be
turned into a domain variable with default bounds.

Note that the gecode implementation of the constraint use
positions starting from 0. An extra dummy element smaller than all
the elements in List is added so that the position returned correspond
to the usual ECLiPSe index starting from 1. In addition, the complexity
of the algorithm used by gecode is linear in time with respect to
Max - Min, where Max and Min are the Maximum and Minimum possible values
for elements in List, respectively. Therefore, this constraint will
behave badly for variables with large domain widths. For a version of this
constraint that uses native Gecode indexing, see sorted_g/3.

ConsistencyModule is the optional module specification to give the
consistency level for the propagation for this constraint:
gfd_bc for bounds consistency.

This constraint is known as sort_permutation in the global
constraint catalog, and is implemented using Gecode's sorted() constraint.

### Modes and Determinism

- sorted(+, ?, ?)
- sorted(?, +, ?)
- sorted(?, ?, +)

## Examples

[eclipse 2]: length(Xs,4),Xs :: 1 .. 100,sorted(Xs, Ys, Ps),Xs = [8, 20|_].
Xs = [8, 20, _715{[1 .. 100]}, _735{[1 .. 100]}]
Ys = [_804{[1 .. 8]}, _824{[1 .. 20]}, _844{[8 .. 100]}, _864{[20 .. 100]}]
Ps = [_969{[1 .. 3]}, _989{[2 .. 4]}, _1009{[1 .. 4]}, _1029{[1 .. 4]}]

## See Also

fd_global : sorted / 3, ic_global : sorted / 3, sorted / 2, ordered / 2, sorted_g / 3