## 5.24. among_diff_0

Origin

Used in the automaton of $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$.

Constraint

$\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚍𝚒𝚏𝚏}_\mathtt{0}\left(\mathrm{𝙽𝚅𝙰𝚁},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

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

$\mathrm{𝙽𝚅𝙰𝚁}$ is the number of variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ that take a value different from 0.

Example
 $\left(3,〈0,5,5,0,1〉\right)$ $\left(0,〈0,0,0,0,0〉\right)$ $\left(1,〈0,0,0,6,0〉\right)$

The first $\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚍𝚒𝚏𝚏}_\mathtt{0}$ constraint holds since exactly 3 values of the collection of values $〈0,5,5,0,1〉$ are different from 0.

Typical
 $\mathrm{𝙽𝚅𝙰𝚁}>0$ $\mathrm{𝙽𝚅𝙰𝚁}<|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>1$ $\mathrm{𝚊𝚝𝚕𝚎𝚊𝚜𝚝}$$\left(1,\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},0\right)$ $2*\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚍𝚒𝚏𝚏}_\mathtt{0}\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$
Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are permutable.

• An occurrence of a value of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ that is different from 0 can be replaced by any other value that is also different from 0.

Arg. properties
• Functional dependency: $\mathrm{𝙽𝚅𝙰𝚁}$ determined by $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

• Contractible wrt. $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ when $\mathrm{𝙽𝚅𝙰𝚁}=0$.

• Contractible wrt. $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ when $\mathrm{𝙽𝚅𝙰𝚁}=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$.

• Aggregate: $\mathrm{𝙽𝚅𝙰𝚁}\left(+\right)$, $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\left(\mathrm{𝚞𝚗𝚒𝚘𝚗}\right)$.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 9 64 625 7776 117649 2097152 43046721

Number of solutions for $\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚍𝚒𝚏𝚏}_\mathtt{0}$: domains $0..n$  Length ($n$)2345678
Total9646257776117649209715243046721
 Parameter value

01111111
1491625364964
24279625054010291792
3-27256125043201200528672
4--25631251944084035286720
5---3125466563529471835008
6----466568235437340032
7-----82354316777216
8------16777216

Solution count for $\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚍𝚒𝚏𝚏}_\mathtt{0}$: domains $0..n$  generalisation: $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}\ne 0$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}\in \mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$).

Keywords
Arc input(s)

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$

Arc generator
$\mathrm{𝑆𝐸𝐿𝐹}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\right)$

Arc arity
Arc constraint(s)
$\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}.\mathrm{𝚟𝚊𝚛}\ne 0$
Graph property(ies)
$\mathrm{𝐍𝐀𝐑𝐂}$$=\mathrm{𝙽𝚅𝙰𝚁}$

Graph model

Since this is a unary constraint we employ the $\mathrm{𝑆𝐸𝐿𝐹}$ arc generator in order to produce an initial graph with a single loop on each vertex.

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

##### Figure 5.24.1. Initial and final graph of the $\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚍𝚒𝚏𝚏}_\mathtt{0}$ constraint  (a) (b)
Automaton

Figure 5.24.2 depicts the automaton associated with the $\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚍𝚒𝚏𝚏}_\mathtt{0}$ constraint. To each variable ${\mathrm{𝚅𝙰𝚁}}_{i}$ of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ corresponds a 0-1 signature variable ${S}_{i}$. The following signature constraint links ${\mathrm{𝚅𝙰𝚁}}_{i}$ and ${S}_{i}$: ${\mathrm{𝚅𝙰𝚁}}_{i}\ne 0⇔{S}_{i}$. The automaton counts the number of variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection that take a value different from 0 and finally assigns this number to $\mathrm{𝙽𝚅𝙰𝚁}$.

##### Figure 5.24.2. Automaton of the $\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚍𝚒𝚏𝚏}_\mathtt{0}$ constraint ##### Figure 5.24.3. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the $\mathrm{𝚊𝚖𝚘𝚗𝚐}_\mathrm{𝚍𝚒𝚏𝚏}_\mathtt{0}$ constraint: since all states variables ${Q}_{0},{Q}_{1},\cdots ,{Q}_{n}$ are fixed to the unique state $s$ of the automaton, the transitions constraints share only the counter variable $C$ and the constraint network is Berge-acyclic 