[ 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

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