Thanks, Guido I used the same with (2), which works pretty good.
On Wed, Jan 13, 2010 at 12:20 PM, Guido Tack <[email protected]> wrote: > 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 > > -- -------------------------------------------- Changbin Liu Computer & Information Science Department University of Pennsylvania Philadelphia, PA U.S.
_______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
