On Wed, Jan 13, 2010 at 6:20 PM, Guido Tack <[email protected]> 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/
_______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
