## 5.344. set_value_precede

Origin
Constraint

$\mathrm{𝚜𝚎𝚝}_\mathrm{𝚟𝚊𝚕𝚞𝚎}_\mathrm{𝚙𝚛𝚎𝚌𝚎𝚍𝚎}\left(𝚂,𝚃,\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

Arguments
 $𝚂$ $\mathrm{𝚒𝚗𝚝}$ $𝚃$ $\mathrm{𝚒𝚗𝚝}$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚜𝚟𝚊𝚛}\right)$
Restrictions
 $𝚂\ne 𝚃$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$
Purpose

If there exists a set variable ${v}_{1}$ of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ such that $𝚂$ does not belong to ${v}_{1}$ and $𝚃$ does, then there also exists a set variable ${v}_{2}$ preceding ${v}_{1}$ such that $𝚂$ belongs to ${v}_{2}$ and $𝚃$ does not.

Example
 $\left(2,1,〈\mathrm{𝚟𝚊𝚛}-\left\{0,2\right\},\mathrm{𝚟𝚊𝚛}-\left\{0,1\right\},\mathrm{𝚟𝚊𝚛}-\varnothing ,\mathrm{𝚟𝚊𝚛}-\left\{1\right\}〉\right)$ $\left(0,1,〈\mathrm{𝚟𝚊𝚛}-\left\{0,2\right\},\mathrm{𝚟𝚊𝚛}-\left\{0,1\right\},\mathrm{𝚟𝚊𝚛}-\varnothing ,\mathrm{𝚟𝚊𝚛}-\left\{1\right\}〉\right)$ $\left(0,2,〈\mathrm{𝚟𝚊𝚛}-\left\{0,2\right\},\mathrm{𝚟𝚊𝚛}-\left\{0,1\right\},\mathrm{𝚟𝚊𝚛}-\varnothing ,\mathrm{𝚟𝚊𝚛}-\left\{1\right\}〉\right)$ $\left(0,4,〈\mathrm{𝚟𝚊𝚛}-\left\{0,2\right\},\mathrm{𝚟𝚊𝚛}-\left\{0,1\right\},\mathrm{𝚟𝚊𝚛}-\varnothing ,\mathrm{𝚟𝚊𝚛}-\left\{1\right\}〉\right)$

The following examples are taken from [Law05]:

• The $\mathrm{𝚜𝚎𝚝}_\mathrm{𝚟𝚊𝚕𝚞𝚎}_\mathrm{𝚙𝚛𝚎𝚌𝚎𝚍𝚎}$$\left(2,1,〈\left\{0,2\right\},\left\{0,1\right\},\left\{\right\},\left\{1\right\}〉\right)$ constraint holds since the first occurrence of value 2 precedes the first occurrence of value 1 (i.e., the set $\left\{0,2\right\}$ occurs before the set $\left\{0,1\right\}$).

• The $\mathrm{𝚜𝚎𝚝}_\mathrm{𝚟𝚊𝚕𝚞𝚎}_\mathrm{𝚙𝚛𝚎𝚌𝚎𝚍𝚎}$$\left(0,1,〈\left\{0,2\right\},\left\{0,1\right\},\left\{\right\},\left\{1\right\}〉\right)$ constraint holds since the first occurrence of value 0 precedes the first occurrence of value 1 (i.e., the set $\left\{0,2\right\}$ occurs before the set $\left\{0,1\right\}$).

• The $\mathrm{𝚜𝚎𝚝}_\mathrm{𝚟𝚊𝚕𝚞𝚎}_\mathrm{𝚙𝚛𝚎𝚌𝚎𝚍𝚎}$$\left(0,2,〈\left\{0,2\right\},\left\{0,1\right\},\left\{\right\},\left\{1\right\}〉\right)$ constraint holds since “there is no set in $〈\left\{0,2\right\},\left\{0,1\right\},\left\{\right\},\left\{1\right\}〉$ that contains 2 but not 0”.

• The $\mathrm{𝚜𝚎𝚝}_\mathrm{𝚟𝚊𝚕𝚞𝚎}_\mathrm{𝚙𝚛𝚎𝚌𝚎𝚍𝚎}$$\left(0,4,〈\left\{0,2\right\},\left\{0,1\right\},\left\{\right\},\left\{1\right\}〉\right)$ constraint holds since no set in $〈\left\{0,2\right\},\left\{0,1\right\},\left\{\right\},\left\{1\right\}〉$ contains value 4.

Typical
 $𝚂<𝚃$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>1$
Arg. properties

Suffix-contractible wrt. $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Algorithm

A filtering algorithm for maintaining value precedence on a sequence of set variables is presented in [YatChiuLawJimmyLee04]. Its complexity is linear to the number of variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

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