Need help with a sorting problem

maxheadroom

Hello everyone, this is my first post in this section, so be gentle

I’m a dabbler with php/mysql, most of the time I’ve been able to figure things out by myself or by searching around a little bit for an answer. I’ve got a conceptual problem I can’t get my head around. I’m not looking for anyone to code this for me, just maybe explain in English the way I should approach the problem.

I have a database application which has a users table, an applications table, and a participants table. The application manages user applications for a series of conferences. Each conference is split into a number of committees. People apply for conferences as part of defined groups (they are in fact secondary school students), and you can’t have more than one user from each group (student from each school) on a committee. When applying, each user chooses their 1st 2nd and 3rd topic preference. Each committee has a defined maximum size, different for each conference. I need a way to maximise the number of people who are given one of their three topic choices without sitting down and manually tweaking over 100 applications per conference.

What I do at the moment is sort the applications in the order they were received, and for each one, check if the choice is valid (nobody else from their school on the committee and committee is not full) and allocate them their highest valid preference, then move on to the next application. I’ve attached the php file responsible for this so you can see the approach I’ve taken. This approach has some advantages: it is conceptually straightforward and it is fair, the earlier you apply the more likely you are to receive your top choice. The disadvantage is that it doesn’t ensure that the maximum number of people get one of their top choices.

I can only imagine that any solution to this would be relatively complex, but it is possible that there is some kind of simple way of thinking about these sorting problems that I don’t know. Any help or pointers would be greatly appreciated.

development.ie

I suggest you create the pseudo code for what you are trying to do, as your explanation indicates you only have 3 tables...users, applications and participants...yet you speak of groups , topics, committees and conferences also.

http://en.wikipedia.org/wiki/Pseudocode there is even an example here of some php and the pseudo code fot it.

Pseudo code is a conceptual way of coding what you are trying to do before you actually implement it....it's design. It is something that is taught when people are starting to write code to get their brains thinking about what they are trying to do first before they get into the detail of implementation in a specific language.

{dev}elopment.ie
Andrew

maxheadroom

development.ie wrote:

I suggest you create the pseudo code for what you are trying to do, as your explanation indicates you only have 3 tables...users, applications and participants...yet you speak of groups , topics, committees and conferences also.

There are other tables, but they're not really relevant to the problem at hand. The application is already running quite well, this is an extra feature I'm trying to add.

The problem is I cant come up with a 'pseudocode' (nice word btw ) solution to this problem. At the moment the 'solution' I have is

get applications recordset

For each row
    If First Preference is OK
        Add user to participants table with first pref
        Change application status to accepted
    OR Else if 2nd Pref is OK
        Add user to participants table with 2nd pref
        Change application status to accepted
    OR Else if 3rd Pref is OK
        Add user to participants table with 3rd pref
        Change application status to accepted
    OR Else
        Increment a counter of apps that cold not be accepted

I'm not even sure what keywords to search for when looking for inspiration. There has to be a better way of approaching this other than testing all possible permutations and seeing which one gives the least number of left over applications?

pH

At first look it appears to be an tough, the only way to find the maximum answer would be to iterate through every possible combination, score it then choose the one with the largest score.

Depending on how many students you have, you could get in to run in n! time by considering every possible arrival order, for n students their applications could have arrived in n! ways.

However, this is something however that a evolutionary algorithm could do very well at:

Find some way of scoring the set, then randomly make changes (valid ones). Discard lower scores, and keep higher ones (use these as the basis for further random changes) and keep going. There are issues to consider like getting stuck on local maxima, and PHP with data in a database is definitely not the best language/environment to do this in but it could work.