Global Constraint Catalog: Celement

5.139. element

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

[VanHentenryckCarillon88]

Constraint

$𝚎𝚕𝚎𝚖𝚎𝚗𝚝 (𝙸𝙽𝙳𝙴𝚇, 𝚃𝙰𝙱𝙻𝙴, 𝚅𝙰𝙻𝚄𝙴)$

Synonyms

$𝚗𝚝𝚑$ , $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚟𝚊𝚛$ , $𝚊𝚛𝚛𝚊𝚢$ .

Arguments

$𝙸𝙽𝙳𝙴𝚇$	$𝚍𝚟𝚊𝚛$
$𝚃𝙰𝙱𝙻𝙴$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚕𝚞𝚎 - 𝚍𝚟𝚊𝚛)$
$𝚅𝙰𝙻𝚄𝙴$	$𝚍𝚟𝚊𝚛$

Restrictions

𝙸𝙽𝙳𝙴𝚇 \geq 1

𝙸𝙽𝙳𝙴𝚇 \leq | 𝚃𝙰𝙱𝙻𝙴 |

| 𝚃𝙰𝙱𝙻𝙴 | > 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚃𝙰𝙱𝙻𝙴, 𝚟𝚊𝚕𝚞𝚎)

Purpose

$𝚅𝙰𝙻𝚄𝙴$ is equal to the ${𝙸𝙽𝙳𝙴𝚇}^{t h}$ item of $𝚃𝙰𝙱𝙻𝙴$ , i.e. $𝚅𝙰𝙻𝚄𝙴 = 𝚃𝙰𝙱𝙻𝙴 [𝙸𝙽𝙳𝙴𝚇]$ .

Example

(3, 〈6, 9, 2, 9〉, 2)

The $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint holds since its third argument $𝚅𝙰𝙻𝚄𝙴 = 2$ is equal to the 3^th ( $𝙸𝙽𝙳𝙴𝚇 = 3$ ) item of the collection $〈 6, 9, 2, 9 〉$ .

All solutions

Figure 5.139.1 gives all solutions to the following non ground instance of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint: $I \in [3, 6]$ , $V \in [1, 9]$ , $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(I, 〈 4, 8, 1, 0, 3, 3, 4, 3 〉, V)$ .

Figure 5.139.1. All solutions corresponding to the non ground example of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint of the All solutions slot

Typical

| 𝚃𝙰𝙱𝙻𝙴 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚃𝙰𝙱𝙻𝙴 . 𝚟𝚊𝚕𝚞𝚎) > 1

Symmetry

All occurrences of two distinct values in $𝚃𝙰𝙱𝙻𝙴 . 𝚟𝚊𝚕𝚞𝚎$ or $𝚅𝙰𝙻𝚄𝙴$ can be swapped; all occurrences of a value in $𝚃𝙰𝙱𝙻𝙴 . 𝚟𝚊𝚕𝚞𝚎$ or $𝚅𝙰𝙻𝚄𝙴$ can be renamed to any unused value.

Arg. properties

Functional dependency: $𝚅𝙰𝙻𝚄𝙴$ determined by $𝙸𝙽𝙳𝙴𝚇$ and $𝚃𝙰𝙱𝙻𝙴$ .
Suffix-extensible wrt. $𝚃𝙰𝙱𝙻𝙴$ .

Usage

See Usage slot of $𝚎𝚕𝚎𝚖$ .

Remark

In the original $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint of CHIP the $𝚒𝚗𝚍𝚎𝚡$ attribute was not explicitly present in the table of values. It was implicitly defined as the position of a value in the previous table.

Within some systems (e.g., Gecode), the index of the first entry of the table $𝚃𝙰𝙱𝙻𝙴$ corresponds to 0 rather than to 1.

When the first entry of the table $𝚃𝙰𝙱𝙻𝙴$ corresponds to a value $p$ that is different from 1 we can still use the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint. We use the reformulation $I = J - p + 1 \land 𝚎𝚕𝚎𝚖𝚎𝚗𝚝 (I, 𝚃𝙰𝙱𝙻𝙴, V)$ , where $I$ and $J$ are domain variables respectively ranging from 1 to $| 𝚃𝙰𝙱𝙻𝙴 |$ and from $p$ to $p + | 𝚃𝙰𝙱𝙻𝙴 | - 1$ .

The $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint is called $𝚗𝚝𝚑$ in Choco (http://choco.sourceforge.net/). It is also sometimes called $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚟𝚊𝚛$ when the second argument corresponds to a table of variables.

The $𝚌𝚊𝚜𝚎$ constraint [Sicstus95] is a generalisation of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint, where the table is replaced by a directed acyclic graph describing the set of solutions: there is a one to one correspondence between the solutions and the paths from the unique source of the dag to its leaves.

Systems

nth in Choco, element in Gecode, element in JaCoP, element in MiniZinc, element in SICStus.

generalisation: $𝚌𝚘𝚗𝚍_𝚕𝚎𝚡_𝚌𝚘𝚜𝚝$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ replaced by $𝚝𝚞𝚙𝚕𝚎$ of $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜$ ).

implied by: $𝚎𝚕𝚎𝚖$ .

implies: $𝚎𝚕𝚎𝚖$ .

related: $𝚝𝚠𝚒𝚗$ ((pairs linked by an element with the same table)).

system of constraints: $𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚜$ .

uses in its reformulation: $𝚌𝚢𝚌𝚕𝚎$ , $𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚜_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ , $𝚜𝚘𝚛𝚝_𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗$ , $𝚝𝚛𝚎𝚎_𝚛𝚊𝚗𝚐𝚎$ , $𝚝𝚛𝚎𝚎_𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎$ .

Keywords

characteristic of a constraint: core, automaton, automaton without counters, reified automaton constraint, derived collection.

constraint arguments: pure functional dependency.

constraint network structure: centered cyclic(2) constraint network(1).

constraint type: data constraint.

filtering: arc-consistency.

heuristics: labelling by increasing cost, regret based heuristics.

modelling: array constraint, table, functional dependency, variable indexing, variable subscript, disjunction, assignment to the same set of values, sequence dependent set-up.

modelling exercises: assignment to the same set of values, sequence dependent set-up, zebra puzzle.

puzzles: zebra puzzle.

Derived Collection

𝚌𝚘𝚕 (\begin{matrix} 𝙸𝚃𝙴𝙼 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚍𝚎𝚡 - 𝚍𝚟𝚊𝚛, 𝚟𝚊𝚕𝚞𝚎 - 𝚍𝚟𝚊𝚛), \\ 𝚒𝚝𝚎𝚖 (𝚒𝚗𝚍𝚎𝚡 - 𝙸𝙽𝙳𝙴𝚇, 𝚟𝚊𝚕𝚞𝚎 - 𝚅𝙰𝙻𝚄𝙴)] \end{matrix})

Arc input(s)

$𝙸𝚃𝙴𝙼$ $𝚃𝙰𝙱𝙻𝙴$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚝𝚎𝚖, 𝚝𝚊𝚋𝚕𝚎)

Arc arity

Arc constraint(s)

• 𝚒𝚝𝚎𝚖 . 𝚒𝚗𝚍𝚎𝚡 = 𝚝𝚊𝚋𝚕𝚎 . 𝚔𝚎𝚢

• 𝚒𝚝𝚎𝚖 . 𝚟𝚊𝚕𝚞𝚎 = 𝚝𝚊𝚋𝚕𝚎 . 𝚟𝚊𝚕𝚞𝚎

Graph property(ies)

𝐍𝐀𝐑𝐂

= 1

Graph model

The original $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint with three arguments. We use the derived collection $𝙸𝚃𝙴𝙼$ for putting together the $𝙸𝙽𝙳𝙴𝚇$ and $𝚅𝙰𝙻𝚄𝙴$ parameters of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint. Within the arc constraint we use the implicit attribute $𝚔𝚎𝚢$ that associates to each item of a collection its position within the collection.

Parts (A) and (B) of Figure 5.139.2 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐀𝐑𝐂$ graph property, the unique arc of the final graph is stressed in bold.

Figure 5.139.2. Initial and final graph of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint


(a)	(b)

Signature

Because of the first condition of the arc constraint the final graph cannot have more than one arc. Therefore we can rewrite $𝐍𝐀𝐑𝐂 = 1$ to $𝐍𝐀𝐑𝐂 \geq 1$ and simplify $\underset{̲}{\bar{𝐍𝐀𝐑𝐂}}$ to $\bar{𝐍𝐀𝐑𝐂}$ .

Automaton

Figure 5.139.3 depicts the automaton associated with the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint. Let ${𝚅𝙰𝙻𝚄𝙴}_{i}$ be the $𝚟𝚊𝚕𝚞𝚎$ attribute of item $i$ of the $𝚃𝙰𝙱𝙻𝙴$ collection. To each triple $(𝙸𝙽𝙳𝙴𝚇, 𝚅𝙰𝙻𝚄𝙴, {𝚅𝙰𝙻𝚄𝙴}_{i})$ corresponds a 0-1 signature variable $S_{i}$ as well as the following signature constraint: $(𝙸𝙽𝙳𝙴𝚇 = i \land 𝚅𝙰𝙻𝚄𝙴 = {𝚅𝙰𝙻𝚄𝙴}_{i}) \Leftrightarrow S_{i}$ .