## 5.117. element

Origin
Constraint

$\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}\left(\mathrm{𝙸𝙽𝙳𝙴𝚇},\mathrm{𝚃𝙰𝙱𝙻𝙴},\mathrm{𝚅𝙰𝙻𝚄𝙴}\right)$

Synonyms

$\mathrm{𝚗𝚝𝚑}$, $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}_\mathrm{𝚟𝚊𝚛}$, $\mathrm{𝚊𝚛𝚛𝚊𝚢}$.

Arguments
 $\mathrm{𝙸𝙽𝙳𝙴𝚇}$ $\mathrm{𝚍𝚟𝚊𝚛}$ $\mathrm{𝚃𝙰𝙱𝙻𝙴}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚕𝚞𝚎}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝚅𝙰𝙻𝚄𝙴}$ $\mathrm{𝚍𝚟𝚊𝚛}$
Restrictions
 $\mathrm{𝙸𝙽𝙳𝙴𝚇}\ge 1$ $\mathrm{𝙸𝙽𝙳𝙴𝚇}\le |\mathrm{𝚃𝙰𝙱𝙻𝙴}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚃𝙰𝙱𝙻𝙴},\mathrm{𝚟𝚊𝚕𝚞𝚎}\right)$
Purpose

$\mathrm{𝚅𝙰𝙻𝚄𝙴}$ is equal to the ${\mathrm{𝙸𝙽𝙳𝙴𝚇}}^{th}$ item of $\mathrm{𝚃𝙰𝙱𝙻𝙴}$.

Example
$\left(3,〈6,9,2,9〉,2\right)$

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

Typical
 $|\mathrm{𝚃𝙰𝙱𝙻𝙴}|>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚃𝙰𝙱𝙻𝙴}.\mathrm{𝚟𝚊𝚕𝚞𝚎}\right)>1$
Symmetry

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

Usage
Remark

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

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

The $\mathrm{𝚌𝚊𝚜𝚎}$ constraint [Sicstus95] is a generalisation of the $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraint, where the table is replaced by a directed acyclic graph describing the set of solutions.

Systems

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

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

Keywords
Derived Collection
$\mathrm{𝚌𝚘𝚕}\left(\begin{array}{c}\mathrm{𝙸𝚃𝙴𝙼}-\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚒𝚗𝚍𝚎𝚡}-\mathrm{𝚍𝚟𝚊𝚛},\mathrm{𝚟𝚊𝚕𝚞𝚎}-\mathrm{𝚍𝚟𝚊𝚛}\right),\hfill \\ \mathrm{𝚒𝚝𝚎𝚖}\left(\mathrm{𝚒𝚗𝚍𝚎𝚡}-\mathrm{𝙸𝙽𝙳𝙴𝚇},\mathrm{𝚟𝚊𝚕𝚞𝚎}-\mathrm{𝚅𝙰𝙻𝚄𝙴}\right)\right]\hfill \end{array}\right)$
Arc input(s)

$\mathrm{𝙸𝚃𝙴𝙼}$ $\mathrm{𝚃𝙰𝙱𝙻𝙴}$

Arc generator
$\mathrm{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚒𝚝𝚎𝚖},\mathrm{𝚝𝚊𝚋𝚕𝚎}\right)$

Arc arity
Arc constraint(s)
 $•\mathrm{𝚒𝚝𝚎𝚖}.\mathrm{𝚒𝚗𝚍𝚎𝚡}=\mathrm{𝚝𝚊𝚋𝚕𝚎}.\mathrm{𝚔𝚎𝚢}$ $•\mathrm{𝚒𝚝𝚎𝚖}.\mathrm{𝚟𝚊𝚕𝚞𝚎}=\mathrm{𝚝𝚊𝚋𝚕𝚎}.\mathrm{𝚟𝚊𝚕𝚞𝚎}$
Graph property(ies)
$\mathrm{𝐍𝐀𝐑𝐂}$$=1$

Graph model

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

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

Signature

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

Automaton

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