[gecode-users] Constrain the number of unique elements

[Guido Tack]

Changbin Liu wrote:

> Hi, Folks:
>     
>    I am wondering whether there is a way to post a constraint on the number of unique elements in a array, e.g
> 
>    I have an IntVarArray, and it may has some identical elements, say it could be [1, 1, 2, 3, 4, 4], and the number of unique elements is 4, since there are 2 "1"s and 2 "4" which are both redundant. If I want to constrain that for a given IntVarArray, it number of unique element can not exceed some value, how can I do that?   I checked "modelling with gecode", seems there is "count" for constraining the number of appearance of elements.

Let's assume the IntVarArray is called x, and we want at most max unique elements.

There are two possible ways to model this:
(1) Use an additional IntVarArray y and a count constraint so that y[i] is the number of occurrences of the ith possible element. Then use reification to get Boolean variables b[i] <-> y[i] > 0, and the number of unique elements will be the sum of the Booleans, which you can constrain to be < max.
(2) Use a SetVar tmp and constrain it to be the union of all x[i]: rel(home, SOT_UNION, x, tmp). Then a cardinality constraint cardinality(home,tmp,0,max) makes sure there's at most max unique elements.

The advantage of (1) should be that you get stronger propagation, but (2) needs only one additional variable and may therefore be more efficient.

Cheers,
	Guido