This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
Re: Grouping with second choice
- To: xsl-list at lists dot mulberrytech dot com, Jeni Tennison <mail at jenitennison dot com>
- Subject: Re: [xsl] Grouping with second choice
- From: Thorsten Liebig <liebig at informatik dot uni-ulm dot de>
- Date: Fri, 17 Aug 2001 14:30:18 +0200
- Organization: Abt. Künstliche Intelligenz, Universität Ulm
- References: <3B6678BA.3B26D933@informatik.uni-ulm.de> <82365671237.20010731141215@jenitennison.com> <3B7CEBB6.10908@informatik.uni-ulm.de> <2612544297.20010817114707@jenitennison.com>
- Reply-To: xsl-list at lists dot mulberrytech dot com
Jeni,
Jeni Tennison wrote:
>
> 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.
You are right, of course. And you might be right, that I should write or
use an optimizing tool rather than a xslt processor. Even though, it is
a fascinating thought using our campus Web interface in that way (register
and divide students and automatically present the results).
The algorithm I want to use is simple indeed:
// supposing the students are sorted by their <RegistrationDate>
// (first come first serve)
for-each <Student>
if ( sum(students in group of <FirstChoice>) < max )
put <Student> in <FirstChoice> group
else
if( sum(students in group of <SecondChoice> < max )
put <Student> in <SecondChoice> group
else
?? use a arbitrary free group ?? (optional)
Thanks
Thorsten
> 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.
--
_____________________________________________________________
Thorsten Liebig Abteilung Künstliche Intelligenz
Tel.: +49 731 502 4207 Fakultät für Informatik
Fax.: +49 731 502 4119 Universität Ulm
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list