[gecode-users] Constrain the number of unique elements

[Mikael Zayenz Lagerkvist]

On Wed, Jan 13, 2010 at 6:20 PM, Guido Tack <tack at gecode.org> wrote:

> 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.
>

There is a variant of this that has the same propagation, but it uses less
constraints and variables so it might be a bit better.

Lets say that you have n variables and that they use k different values. If
you count the number of zeroes in the y-array (one count constraint), you
get a value z which is equal to n-k. To constrain the maximum number of
values, just make sure that there is a minumum number of zeroes: z >= n-max.

Cheers,
Mikael

-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20100114/89def89b/attachment.htm>