This is the mail archive of the xsl-list@mulberrytech.com mailing list .


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: Grouping with second choice


Hi Thorsten,

> Thanks for the hint. But what I intend to do, is to divide the
> students according to there choices *and* additional constraints
> like maximum group size. So, whenever a first choice cannot be
> fulfilled due to group size reasons the second choice should be
> taken into account. My problem is (I think), that all those
> solutions do not apply in which the group tags are created on the
> fly (like in the solution below) because it may happen that a
> student has to be divided in a group which hasn't been created, yet.
> Concrete, having a maximal group size of 3, the students of my
> example file should be classified as follows:

Oh, I see. This kind of assignment problem is notoriously difficult to
solve because you have to balance up the sizes of so many groups
against the preferences of lots of people to get an optimal solution.
It's something that's typically done by an expert system rather than a
conventional application.

For example, if you have students A, B, C, D, E, F and G, and groups
1, 2 and 3. A, B, C and D's first choice is 1. E, F and G's first
choice is 2. To decide which of A, B, C and D should not get their
first choice, you have to look at what their second choice is and know
how many people there are already in that group. If A's second choice
is group 2, and B's second choice is group 3, then B should be moved
into group 3 rather than A being moved into group 2 and therefore
making it too large. Plus there might be extra constraints, like the
fact that you might be able to squeeze one or two extra students into
a group if it makes everyone happier, or you might not want to have
too few students in a group either.

Probably the best thing as a starting point would be to convert your
XML into something that looked like:

<group1>
  <student pref="1">A</student>
  <student pref="2">B</student>
  <student pref="1">C</student>
</group1>
<group2>
  <student pref="2">A</student>
  <student pref="1">B</student>
  <student pref="2">C</student>
</group2>

You can do this by creating a key that indexes the students by first
*or* second choice:

<xsl:key name="students" match="Student"
         use="FirstChoice | SecondChoice" />

and then creating groups from that with:

<xsl:template match="Course">
  <Classification>
    <xsl:for-each select="Student[count(.|key('students',
                                              FirstChoice)[1]) = 1]">
      <xsl:call-template name="CreateGroup">
        <xsl:with-param name="group" select="FirstChoice" />
      </xsl:call-template>
    </xsl:for-each>
    <xsl:for-each select="Student[count(.|key('students',
                                              SecondChoice)[1]) = 1]">
      <xsl:call-template name="CreateGroup">
        <xsl:with-param name="group" select="SecondChoice" />
      </xsl:call-template>
    </xsl:for-each>
  </Classification>
</xsl:template>

<xsl:template name="CreateGroup">
  <xsl:param name="group" />
  <xsl:element name="{$group}">
    <xsl:for-each select="key('students', $group)">
      <xsl:sort select="RegistrationDate" />
      <xsl:variable name="choice">
        <xsl:choose>
          <xsl:when test="FirstChoice = $group">1</xsl:when>
          <xsl:otherwise>2</xsl:otherwise>
        </xsl:choose>
      </xsl:variable>
      <Student pref="{$choice}">
        <xsl:copy-of select="node()" />
      </Student>
    </xsl:for-each>
  </xsl:element>
</xsl:template>

You will then be able to refine that XML more easily to get the group
sizes that you want.

On the other hand, perhaps I'm over-complicating it and you have a
simple algorithm for assigning students to groups to get the
requisite group sizes. If you can write it down in pseudo-code we
could probably turn it into XSLT.

Cheers,

Jeni

---
Jeni Tennison
http://www.jenitennison.com/


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]