Arrays of Variables

Interestingly, XCSP³ allows us to declare k-dimensional arrays of variables, with $k \geq 1$, by introducing elements array inside variables. The general (simplified) syntax for arrays is :

Syntax

 <array id="identifier"  [ type="varType" ]  size="dimensions"  [ startIndex="integer" ]> 
  ...
</array>

Hence, for each such element, there is a required attribute id and a required attribute size whose value gives the structure of the array under the form $[nb_1]...[nb_p]$ with $nb_1, \ldots, nb_p$ being strictly positive integers. The number of dimensions of an array is the number of pairs of opening/closing square brackets, and the size of each dimension is given by its bracketed value. For example, if x is an array of 10 variables, you just write [10], and if y is a 2-dimensional array, 5 rows by 8 columns, you write [5][8]. Indexing used for any dimension of an array starts at 0, unless the (optional) attribute startIndex gives another value. Of course, it is possible to define arrays of any kind of variables, as e.g., arrays of symbolic variables, arrays of set variables, etc. by using the attribute type: all variables of an array have the same type. The content of an element array of a specified type is defined similarly to the content of an element var of the same type, and basically, all variables of an array have the same domain, except if mixed domains are introduced (as shown below and in the full specifications).

To define an array x of 10 integer variables with domain 1..100 and a 2-dimensional array y (5 * 8) of 0/1 variables, we write:

Example

<array id="x" size="[10]"> 1..100 </array> 

<array id="y" size="[5][8]"> 0 1 </array>

Importantly, it is necessary to be able to identify variables in arrays. We simply use the classical [] notation, with indexing starting at 0 (unless another value is given by startIndex). For example, assuming that 0 is the ``starting index’’, x[0] is the first variable of the array x, and y[4][7] the last variable of the array y.

In XCSP³-core, only arrays of integer variables (including of course 0/1 variables) are allowed, and the value of the attribute startIndex is always 0.

Using Compact Forms

Sometimes, one is interested in selecting some variables from an array, for example, the variables in the first row of a 2-dimensional array. We use integer intervals for that purpose, as in x[3..5] and y[2..3][0..1], and we refer to such expressions as compact lists of array variables. In a context where a list of variables is expected, it is possible to use this kind of notation, and the result is then considered to be a list of variables, ordered according to a lexicographic order < on index tuples (for example y[2][4] is before y[2][5] since (2,4) < (2,5)). On our previous example, in a context where a list of variables is expected, x[3..5] denotes the list of variables x[3], x[4] and x[5], while y[2..3][0..1] denotes the list of variables y[2][0], y[2][1], y[3][0] and y[3][1]. It is also possible to omit an index, with a meaning similar to using 0..s where s denotes the largest possible index. For example, y[2][] is equivalent to y[2][0..7].

Finally, one may wonder how compact lists of array variables (such as x[3..5], y[2..3][0..1], x[], y[][]) precisely expand in the context of the XCSP³ elements that will be presented in the next sections. The rule is the following:

If a 2-dimensional compact list (such as y[][]) appears in an element , the compact list expands as a sequence of tuples (one tuple per row, with variables of the row separated by a comma, enclosed between parentheses). For example,

Example

 <matrix>
  y[][]
</matrix>

expands as:

Example

 <matrix> 
   (y[0][0],y[0][1],...,y[0][7]) 
   (y[1][0],y[1][1],...,y[1][7])
   ...
   (y[4][0],y[4][1],...,y[4][7])
</matrix>

In all other situations, the compact list expands as a list of variables, with whitespace as a separator. For example, we have:

Example

  <list>
    y[2..3][0..1]
</list>

that expands as:

Example

 <list>
  y[2][0] y[2][1] y[3][0] y[3][1]
</list>

Using this rule, it is always possible to expand all compact lists of array variables in order to get a form of the problem instance with only references to simple variables.

Dealing With Mixed Domains

Sometimes, the variables from the same array naturally have mixed domains. One solution is to build a large domain that can be suitable for all variables, and then to post unary domain constraints. But this not very satisfactory.

Another solution with XCSP³ is to insert the different definitions of domains inside the array element. When several subsets of variables of an array have different domains, we simply have to put an element domain for each of these subsets. An attribute for indicates the list of variables to which the domain definition applies. The value of for can be a sequence (whitespace as separator) of variable identifiers (with compact forms authorized), or the special value others, which is used to declare a default domain. Only one element domain can have its attribute for set to others, and if it is present, it is necessary at the last position. The syntax for arrays that involve variables with different domains is:

Syntax

 <array id="identifier"  [ type="varType" ]  size="dimensions"  [ startIndex="integer" ]>
        (<domain for="(intVar wspace)+"> ... </domain>)+
        [<domain for="others"> ... </domain>]
 </array> 

As an illustration, the 2-dimensional array x below is such that the variables of the first, second and third rows have 1..10, 1..20 and 1..15 as domains, respectively. Also, all variables of array y have {2,4,6} as domain except for y[4] whose domain is {0,1}. Finally, all variables of array z have {0,1} as domain except for the variables that belong to the lists z[][0..1][] and z[][2][2..4].

Example

 <array id="x" size="[3][5]"> 
  <domain for="x[0][]"> 1..10 </domain>
  <domain for="x[1][]"> 1..20 </domain>
  <domain for="x[2][]"> 1..15 </domain>
</array> 
<array id="y" size="[10]"> 
  <domain for="y[4]"> 0 1 </domain> 
  <domain for="others"> 2 4 6 </domain>
</array> 
<array id="z" size="[5][5][5]"> 
  <domain for="z[][0..1][] z[][2][2..4]"> 0..10 </domain> 
  <domain for="others"> 0 1 </domain>
</array>