Re: [xsl] Grouping with second choice

[Thorsten Liebig <liebig at informatik dot uni-ulm dot de>]

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