[gecode-users] Constrain the number of unique elements

[Changbin Liu]

Thanks, Guido

I used the same with (2), which works pretty good.

On Wed, Jan 13, 2010 at 12:20 PM, Guido Tack <tack at gecode.org> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20100114/2f8a17f0/attachment.htm>