[gecode-users] Defining constraint to extract Element from an array of integer holding repeated values
Guido Tack
tack at ps.uni-sb.de
Sun Jan 11 19:03:08 CET 2009
Jeffrey Mak wrote:
> How to defining constraint to extract Element from an array of
> integer holding repeated values?
> Gecode provide ElementUnion function to extract elements from IntSet
> or VarSet.
> How about an integer array in which elements may hold the same values?
>
> Below is a hypothesized problem that needs such capabilities:
>
> Assign n number of students into 3 groups.
> each student is teach by a certain instructor.
>
> I'd like to evenly distributed the students into the groups (assume
> the total no. of student is divisible by the 3 groups.)
> Given an array where the 1st element holds the instructor (in enum)
> of the 1st student and so on...
>
> How should I model the constratint to enforce that:
> for each group, the total no. of distinct instructors are the
> same.
If I understand the problem correctly, the mapping from student to
instructor is given in advance, as an array mapping student id to
instructor id. Then a model for this problem may look as follows:
Use a SetVarArray group, so that group[i] is the set of students in
group i. Now we have to map from students to instructors. For this,
we use the elementsUnion constraint with IntSetArgs. Construct the
IntSetArgs isa such that isa[j] is an IntSet that contains as the
single element the instructor of student number j. Then
elementsUnion(this, isa, group[i], x) will bind x to the set of
instructors of group i. Using cardinality(this, x,y) constrains an
IntVar y to the cardinality of x. So balancing all the y (one for
each group) solves the problem.
Hope this helps,
Guido
More information about the gecode-users
mailing list