Link Search Menu Expand Document
Specifications PyCSP3 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$})

ordered($X$,$\odot$) with $X=\langle x_1,x_2,\ldots \rangle$ and $\odot \in \{ \lt,\leq,\geq,\gt \}$, iff $\forall i : 1 \leq i \lt |X|, x_i \odot x_{i + 1}$

Syntax

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

The constraint below is equivalent to x1 $\lt$ x2 $\lt$ x3 $\lt$ x4.

Example

<ordered> 
  <list> x1 x2 x3 x4 </list> 
  <operator> lt </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, 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 XCSP3 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>