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
_______________________________________________
Gecode users mailing list
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
