Specifications PyCSP³ Tools Instances Competitions About

Constraint Ordered

The constraint ordered ensures that the variables of list are ordered in sequence according to a relational operator specified in operator whose value must be in {lt,le,ge,gt} (for {$\lt,\le,\ge,\gt$}). The optional element lengths indicates the minimum distances between any two successive variables of list.

ordered($X$,$L$,$\odot$), with $X=\langle x_1,x_2,\ldots \rangle$, $L=\langle l_1,l_2,\ldots \rangle$ and $\odot \in \{<,\leq,\geq,>\}$, iff $\forall i : 1 \leq i < |X|, x_i + l_i \odot x_{i+1}$
ordered($X$,$\odot$), with $X=\langle x_1,x_2,\ldots \rangle$ and $\odot \in \{<,\leq,\geq,>\}$, iff $\forall i : 1 \leq i < |X|, x_i \odot x_{i+1}$ Prerequisite: |X| = |L| + 1

Syntax

<ordered>
  <list> (intVar wspace)2+ </list>
  [<lengths> (intVal wspace)2+ | (intVar wspace)2+ </lengths>] 
  <operator> "lt" | "le" | "ge" | "gt" </operator>
</ordered> 

The first constraint below is equivalent to x1 $\lt$ x2 $\lt$ x3 $\lt$ x4, and the second one is equivalent to y1 + 5 $\geq$ y2 $\land$ y2 + 3 $\geq$ y3.

Example

<ordered> 
  <list> x1 x2 x3 x4 </list> 
  <operator> lt </operator>
</ordered>
<ordered> 
  <list> y1 y2 y3  </list>
  <lengths> 5 3 </lengths>
  <operator> ge </operator>
</ordered>

The constraints from the Global Constraints Catalog that are captured by ordered are:

increasing, strictly_increasing
decreasing, strictly_decreasing

As a matter of fact, if the element lengths is absent, one can define a constraint ordered without using the element operator it suffices to add a special attribute case to ordered. This way, the opening and closing tags of list become optional, making the XCSP³ representation more compact.

Syntax

<ordered case="orderedType"> (intVar wspace)2+ </ordered>   <!-- Simplified Form -->

The possible values for the attribute case are increasing, strictlyIncreasing, decreasing and strictlyDecreasing. The constraint introduced above can then be written:

Syntax

<ordered id="c" case="strictlyIncreasing"> x1 x2 x3 x4 </ordered>

In the future, the format might be extended to include an element specifying the order (preferences between values) to follow.

Variant ordered-list (and lex)

The constraint ordered can be naturally lifted to lists (and also, sets and multisets). Because this constraint is very popular, it is allowed to use lex instead of ordered over lists of integer variables. The constraint lex ensures that the tuple formed by the values assigned to the variables of the first element list is related to the tuple formed by the values assigned to the variables of the second element list with respect to the operator specified in operator. If more than two elements list are given, the entire sequence of tuples must be ordered; this captures then lexChain.

For the semantics, we consider that $X=[ X_1,X_2,\ldots,X_n ]$, with each $X_i$ being a list of variables.

lex($X$,$\odot$) with $X=\langle X_1,X_2,\ldots \rangle$ and $\odot \in \{ \lt_{lex}, \leq_{lex}, \geq_{lex}, \gt_{lex} \}$, iff $\forall i : 1 \leq i \lt |X|, X_i \odot X_{i+1}$

Syntax

<lex>
  (<list> (intVar wspace)2+ </list>)2+
  <operator> "lt" | "le" | "ge" | "gt" </operator>
</lex>

In the following example, the first constraint states that $\langle$ x1,x2,x3,x4 $\rangle$ $\leq_{lex}$ $\langle$ y1,y2,y3,y4 $\rangle$, whereas the second one states that $\langle$z1,z2,z3$\rangle$ $\lt_{lex}$ $\langle$ z4,z5,z6 $\rangle$ $\gt_{lex}$ $\langle$ z7,z8,z9 $\rangle$.

Example

<lex>
  <list> x1 x2 x3 x4 </list>
  <list> y1 y2 y3 y4 </list>
  <operator> le </operator>
</lex>
<lex>
  <list> z1 z2 z3 </list>
  <list> z4 z5 z6 </list>
  <list> z7 z8 z9 </list>
  <operator> gt </operator>
</lex>

Variant ordered-matrix

The constraint ordered-matrix, that could be called lex-matrix too, corresponds to lex2 in the literature. It ensures that, for a given matrix of variables, both adjacent rows and adjacent columns are lexicographically ordered. For the syntax, we can use lex instead of ordered as for ordered-list.

It admits a parameter $M=[ X_1,X_2,\ldots,X_n ]$, with $X_1=\langle x_{1,1},x_{1,2},\ldots,x_{1,m} \rangle$, $X_2=\langle x_{2,1},x_{2,2},\ldots,x_{2,m} \rangle$, $\ldots$, given by an element matrix, assuming here a matrix of size $n \times m$

lex-matrix($M$,$\odot$) with $M=[X_1,X_2,\ldots X_n]$ and $\odot \in \{ \lt,\leq,\geq,\gt \}$, iff

lex$(\langle M[1],\ldots,M[n] \rangle,\odot)$ holds
lex$(\langle M^T[1],\ldots,M^T[m] \rangle,\odot)$ holds

Syntax

<lex>
  <matrix> ("(" intVar ("," intVar)+ ")")2+ </matrix>
  <operator> "lt" | "le" | "ge" | "gt" </operator>
</lex>

In the following example, the constraint states that:

$\langle$ z1,z2,z3 $\rangle$ $\leq_{lex}$ $\langle$ z4,z5,z6 $\rangle$ $\leq_{lex}$ $\langle$ z7,z8,z9 $\rangle$
$\langle$ z1,z4,z7 $\rangle$ $\leq_{lex}$ $\langle$ z2,z5,z8 $\rangle$ $\leq_{lex}$ $\langle$ z3,z6,z9 $\rangle$

Example

<lex>
  <matrix> 
    (z1,z2,z3)
    (z4,z5,z6)
    (z7,z8,z9)
  </matrix>
  <operator> le </operator>
</lex>

If instead of having 9 variables z1,z2,… we declare a two-dimensional array z[][], then we can simply write:

Example

<lex>
  <matrix> 
    z[][] 
  </matrix>
  <operator> le </operator>
</lex>