[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,


More information about the gecode-users mailing list