5.117. element

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

[VanHentenryckCarillon88]

Constraint

πšŽπš•πšŽπš–πšŽπš—πš(π™Έπ™½π™³π™΄πš‡,πšƒπ™°π™±π™»π™΄,πš…π™°π™»πš„π™΄)

Synonyms

πš—πšπš‘, πšŽπš•πšŽπš–πšŽπš—πš_πšŸπšŠπš›, πšŠπš›πš›πšŠπš’.

Arguments
π™Έπ™½π™³π™΄πš‡πšπšŸπšŠπš›
πšƒπ™°π™±π™»π™΄πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•πšžπšŽ-πšπšŸπšŠπš›)
πš…π™°π™»πš„π™΄πšπšŸπšŠπš›
Restrictions
π™Έπ™½π™³π™΄πš‡β‰₯1
π™Έπ™½π™³π™΄πš‡β‰€|πšƒπ™°π™±π™»π™΄|
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπ™°π™±π™»π™΄,πšŸπšŠπš•πšžπšŽ)
Purpose

πš…π™°π™»πš„π™΄ is equal to the π™Έπ™½π™³π™΄πš‡ th item of πšƒπ™°π™±π™»π™΄.

Example
(3,6,9,2,9,2)

The πšŽπš•πšŽπš–πšŽπš—πš constraint holds since its third argument πš…π™°π™»πš„π™΄=2 is equal to the 3th (π™Έπ™½π™³π™΄πš‡=3) item of the collection 〈6,9,2,9βŒͺ.

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.

Usage

See πšŽπš•πšŽπš–.

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.

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.

Systems

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

See also

common keyword: πšŽπš•πšŽπš–_πšπš›πš˜πš–_𝚝𝚘, πšŽπš•πšŽπš–πšŽπš—πš_πšπš›πšŽπšŠπšπšŽπš›πšŽπšš, πšŽπš•πšŽπš–πšŽπš—πš_πš•πšŽπšœπšœπšŽπšš, πšŽπš•πšŽπš–πšŽπš—πš_πš–πšŠπšπš›πš’πš‘, πšŽπš•πšŽπš–πšŽπš—πš_πš™πš›πš˜πšπšžπšŒπš, πšŽπš•πšŽπš–πšŽπš—πš_πšœπš™πšŠπš›πšœπšŽΒ (array constraint), πšŽπš•πšŽπš–πšŽπš—πšπš—, πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšœπš™πšŠπš›πšœπšŽ, πš’πš—_πš›πšŽπš•πšŠπšπš’πš˜πš—, 𝚜𝚝𝚊𝚐𝚎_πšŽπš•πšŽπš–πšŽπš—πš, πšœπšžπš–Β (data constraint).

generalisation: πšŒπš˜πš—πš_πš•πšŽπš‘_𝚌𝚘𝚜𝚝 (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšπšžπš™πš•πšŽ of πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ).

implied by: πšŽπš•πšŽπš–.

implies: πšŽπš•πšŽπš–.

system of constraints: πšŽπš•πšŽπš–πšŽπš—πšπšœ.

uses in its reformulation: πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πšπš›πšŽπšŽ_πš›πšŠπš—πšπšŽ, πšπš›πšŽπšŽ_πš›πšŽπšœπš˜πšžπš›πšŒπšŽ.

Keywords

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

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

constraint type: data constraint.

filtering: arc-consistency.

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
πšŒπš˜πš•π™Έπšƒπ™΄π™Ό-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πšπšŸπšŠπš›,πšŸπšŠπš•πšžπšŽ-πšπšŸπšŠπš›),πš’πšπšŽπš–(πš’πš—πšπšŽπš‘-π™Έπ™½π™³π™΄πš‡,πšŸπšŠπš•πšžπšŽ-πš…π™°π™»πš„π™΄)]
Arc input(s)

π™Έπšƒπ™΄π™Ό πšƒπ™°π™±π™»π™΄

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πšπšŽπš–,πšπšŠπš‹πš•πšŽ)

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.117.1 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.117.1. Initial and final graph of the πšŽπš•πšŽπš–πšŽπš—πš constraint
ctrs/elementActrs/elementB
(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 𝐍𝐀𝐑𝐂β‰₯1 and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.

Automaton

FigureΒ 5.117.2 depicts the automaton associated with the πšŽπš•πšŽπš–πšŽπš—πš constraint. Let πš…π™°π™»πš„π™΄ i be the πšŸπšŠπš•πšžπšŽ attribute of the i th item of the πšƒπ™°π™±π™»π™΄ collection. To each triple (π™Έπ™½π™³π™΄πš‡,πš…π™°π™»πš„π™΄,πš…π™°π™»πš„π™΄ i ) corresponds a 0-1 signature variable πš‚ i as well as the following signature constraint: (π™Έπ™½π™³π™΄πš‡=iβˆ§πš…π™°π™»πš„π™΄=πš…π™°π™»πš„π™΄ i )β‡”πš‚ i .

Figure 5.117.2. Automaton of the πšŽπš•πšŽπš–πšŽπš—πš constraint
ctrs/element1
Figure 5.117.3. Hypergraph of the reformulation corresponding to the automaton of the πšŽπš•πšŽπš–πšŽπš—πš constraint
ctrs/element2