4.2.2.3. Sorting constraints

In this section: arg_sort, decreasing, increasing, sort, strictly_decreasing, strictly_increasing.

arg_sort

1.  predicate arg_sort(array [$$E] of var int: x,
                       array [int] of var $$E: p)

2.  predicate arg_sort(array [$$E] of var float: x,
                       array [int] of var $$E: p)

3.  function array [int] of var $$E: arg_sort(array [$$E] of var int: x)

4.  function array [int] of var $$E: arg_sort(array [$$E] of var float: x)
1, 2.

Constrains p to be the permutation which causes x to be in sorted order hence x[p[i]] <= x[p[i+1]].

The permutation is the stable sort hence x[p[i]] = x[p[i+1]] \(\rightarrow\) p[i] < p[i+1].

3, 4.

Returns the permutation p which causes x to be in sorted order hence x[p[i]] <= x[p[i+1]].

The permutation is the stable sort hence x[p[i]] = x[p[i+1]] \(\rightarrow\) p[i] < p[i+1].

decreasing

predicate decreasing(array [$X] of var bool: x)
predicate decreasing(array [$X] of var float: x)
predicate decreasing(array [$X] of var int: x)
predicate decreasing(array [$X] of var set of int: x)
Requires that the array x is in decreasing order (duplicates are allowed).

increasing

predicate increasing(array [$X] of var bool: x)
predicate increasing(array [$X] of var float: x)
predicate increasing(array [$X] of var int: x)
predicate increasing(array [$X] of var set of int: x)
Requires that the array x is in increasing order (duplicates are allowed).

sort

1.  predicate sort(array [int] of var int: x, array [int] of var int: y)

2.  function array [int] of var int: sort(array [int] of var int: x)
  1. Requires that the multiset of values in x are the same as the multiset of values in y but y is in sorted order.

  2. Return a multiset of values that is the same as the multiset of values in x but in sorted order.

strictly_decreasing

predicate strictly_decreasing(array [$X] of var bool: x)
predicate strictly_decreasing(array [$X] of var int: x)
predicate strictly_decreasing(array [$X] of var opt int: x)
Requires that the array x is in a stricly decreasing order (duplicates are not allowed).

strictly_increasing

predicate strictly_increasing(array [$X] of var bool: x)
predicate strictly_increasing(array [$X] of var int: x)
predicate strictly_increasing(array [$X] of var opt int: x)
Requires that the array x is in a stricly increasing order (duplicates are not allowed).