## 5.257. min_nvalue

Origin

N.Β Beldiceanu

Constraint

$\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi Ό\pi Έ\pi ½},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Arguments
 $\mathrm{\pi Ό\pi Έ\pi ½}$ $\mathrm{\pi \pi \pi \pi }$ $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$
Restrictions
 $\mathrm{\pi Ό\pi Έ\pi ½}\beta ₯1$ $\mathrm{\pi Ό\pi Έ\pi ½}\beta €|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$
Purpose

$\mathrm{\pi Ό\pi Έ\pi ½}$ is the minimum number of times that the same value is taken by the variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Example
 $\left(2,β©9,1,7,1,1,7,7,7,7,9βͺ\right)$ $\left(5,β©8,8,8,8,8βͺ\right)$ $\left(2,β©1,8,1,8,1βͺ\right)$

In the first example, values $1,7,9$ are respectively used $3,5,2$ times. So the minimum number of time $\mathrm{\pi Ό\pi Έ\pi ½}$ that a same value occurs is 2. Consequently the corresponding $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint holds.

Typical
 $2*\mathrm{\pi Ό\pi Έ\pi ½}\beta €|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$ $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>1$ $\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)>1$
Symmetries
• Items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are permutable.

• All occurrences of two distinct values of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ can be swapped; all occurrences of a value of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ can be renamed to any unused value.

Arg. properties

Functional dependency: $\mathrm{\pi Ό\pi Έ\pi ½}$ determined by $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Usage

This constraint may be used in order to replace a set of $\mathrm{\pi \pi \pi \pi \pi }$ or $\mathrm{\pi \pi \pi \pi \pi }$ constraints were one would have to generate explicitly one constraint for each potential value. Also useful for constraining the number of occurrences of the less used value without knowing this value in advance and without giving explicitly a lower limit on the number of occurrences of each value as it is done in the $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi ’}$ constraint.

Reformulation

Assume that $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ is not empty. Let $\mathrm{\Xi ±}$ and $\mathrm{\Xi ²}$ respectively denote the smallest and largest possible values that can be assigned to the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection. Let the variables ${O}_{\mathrm{\Xi ±}},{O}_{\mathrm{\Xi ±}+1},\beta ―,{O}_{\mathrm{\Xi ²}}$ respectively correspond to the number of occurrences of values $\mathrm{\Xi ±},\mathrm{\Xi ±}+1,\beta ―,\mathrm{\Xi ²}$ within the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection. The $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint can be expressed as the conjunction of the following two constraints:

Β Β Β $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi ’}$ $\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\beta ©\mathrm{\pi \pi \pi }-\mathrm{\Xi ±}\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }-{O}_{\mathrm{\Xi ±}},$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-\mathrm{\Xi ±}+1\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }-{O}_{\mathrm{\Xi ±}+1},$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\beta ―$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-\mathrm{\Xi ²}\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }-{O}_{\mathrm{\Xi ²}}\beta ͺ\right)$,

Β Β Β $\mathrm{\pi \pi \pi }_\mathrm{\pi }$$\left(\mathrm{\pi Ό\pi Έ\pi ½},1,\beta ©0,{O}_{\mathrm{\Xi ±}},{O}_{\mathrm{\Xi ±}+1},\beta ―,{O}_{\mathrm{\Xi ²}}\beta ͺ\right)$.

We use a $\mathrm{\pi \pi \pi }_\mathrm{\pi }$ constraint (with its $\mathrm{\pi \pi °\pi ½\pi Ί}$ parameter set to 1) instead of a $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraint in order to discard the smallest value 0.

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

Number of solutions for $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$: domains $0..n$

Length ($n$)2345678
Total9646257776117649209715243046721
 Parameter value

16605607470113442205872842473664
23-60300378036456566496
3-4--42019604032
4--5---2520
5---6---
6----7--
7-----8-
8------9

Solution count for $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$: domains $0..n$

Keywords
Cond. implications

$\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi Ό\pi Έ\pi ½},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Β Β Β  withΒ  $\mathrm{\pi Ό\pi Έ\pi ½}<|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$

Β Β implies $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi ½\pi  \pi °\pi »},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Β Β Β  whenΒ  $\mathrm{\pi ½\pi  \pi °\pi »}=2$.

Arc input(s)

$\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$

Arc generator
$\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi }=\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi }$
Graph property(ies)
$\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$$=\mathrm{\pi Ό\pi Έ\pi ½}$

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.257.1 respectively show the initial and final graph associated with the first example of the Example slot. Since we use the $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ graph property, we show the smallest strongly connected component of the final graph associated with the first example of the Example slot.

Automaton

FigureΒ 5.257.2 depicts the automaton associated with the $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint. To each item of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ corresponds a signature variable ${S}_{i}$ that is equal to 0.