[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

Re: [xsl] Grouping with second choice

---

---

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

---