Algorithm for sorting people by room depending on age and nationality

Question

I am working on a program for an English school in which I work. Im not paid, it's just a kind of hobby to improve / automate my workflow.

His residential school and one of the aspects that I look at automation is how we set aside a room for students, and although I don't want a completely hyped solution, I was hoping someone could point me in the right direction ... Suggestions on how you might approach this or by offering viewing algorithms, etc.

Mostly at school we have a whole bunch of different rooms - from singles to dormitories for 8 people. We get many different nationalities from around the world, and we always try to have many nationalities in each issue. Where there is more than one nationality, we try to balance them. Age is also important, we always put students of the same age together, still trying to mix nationalities, and it is unusual for us that students share with them more than two years between them.

I assume that, more generally, I am interested in how to sort a given set of students based on two parameters with an optimal result with a few attached rules.

I hope that I will clearly explain what I'm trying to achieve ... so it sounds very simple, but I'm trying to think about how to do it in a simple way, that is, by sorting by nationality and then by age, but it just isn’t Cut it, and I know there must be a better way to get close to it. When I do this “manually” on an excel sheet, it feels quite intuitive.

Thanks to everyone who offers help / advice.

Answer 1

This is an interesting question, but it is not easy to answer. Somehow this is due to the packaging of subdivsion and bin or the problem of the cutting tool. You can also search for a topological view. You can find the Drools business logic platform that allows you to define such rules.

Answer 2

First of all, it may seem interesting to you: A stable problem with neighbors (Wikipedia) . Unfortunately, it does not answer your question.

Try the genetic algorithm .

There are three main criteria for using a genetic algorithm:

• the ability to represent a solution as a mutable array. We can have an array of integers, so [i] is the place for the i-th student.

• mutation of the state should give predictable results. In our case, this is true. Mutation of the array will predictably mix students between rooms.

• easy to write fast fitness function. It should not be too difficult to write an O (n) fitness function.

This is an interesting problem. I will try to write code with this approach, and we will see what happens.

Answer 3

How about what you think of the room as something that pushes students away from the nationality that it already has and attracts students of close age to what it already has. The closer the age to middle age, the more he attracts him, and the more guys of ethnicity X are in the room, the more repels children from X ethnicity.

Then you would have each new student added, repeat each room and see which one attracts her more. I think if the room is empty, you can set all the forces to 0. In addition, you will have a pair of constants that multiply each of the two “forces” so that you can calibrate it depending on how important it is to have one age against of how important it is to have different nationalities.

Answer 4

I would analyze each student and create a “personality” vector based on his age and nationality. Then I sorted the vectors and maybe distorted the results a bit after sorting to encourage diversity.

Answer 5

The general theme of “assign x for y by constraints when optimizing a certain value” refers to operations research or, more specifically, http://en.wikipedia.org/wiki/Mathematical_optimization . A common approach is to officially identify the problem and use a common an optimization solver, such as one listed at http://en.wikipedia.org/wiki/List_of_optimization_software .

Try it, the official specification languages ​​for using existing solvers are quite easy to learn, and you can get the best solution without having to debug a complex algorithm.

Answer 6

Wording as a general optimization problem

It will be useful to formalize restrictions and parameters. Suppose that for 1 <= i <= 8 we have numbers n_i of size i. Now let's impose a strict restriction, which in a particular room S, every two students a, b \ in S, we have the following:

|Grade(a) - Grade(b)| <= 2 (1) 

Now we are interested in optimizing the “diversity” function, which intuitively introduces the idea that we want the rooms to be as mixed as possible. Therefore, we can present this goal as:

 max over all arrangements {{ Sum over all rooms S of DiversityScore(S) }} where we have DiversityScore(S) = # of Different Nationalities in the Room 

Wording as a graph problem

This is the most common setting, but obviously max on all devices is not feasible. Now we pose this as a graph problem with tight restrictions. We designate all students as a vertex in column G. Connect two vertices if the students satisfy restriction (1). Now a click on this graph represents a group of students who can be placed in one room. Now go on eagerly. Select the largest click of size 4, which has the largest measure of diversity. Then place them in the room and continue until all the rooms are full. This click search method may also include gender restrictions, which are useful, but not that click search is a difficult NP task.

Now, before trying to come up with something that can be faster, let's think about how to relax the tight constraint (1). We can massage our graph shape by including the edges of the weight in the image. Thus, if a strict restriction is met, we denote the weight of the edge from i to j as 1. If two students i and j deviate in age more than 2, this means that the weight of the edge is 1 / (age difference) ^ 2 or something like that. Then the click estimate should be the product of crossing with clicks with a certain amount of points. However, it becomes clear that now the problem lies in the full schedule, which is only a general optimization, which we hoped to avoid, so we need to impose some strict restrictions to reduce the connectivity of our schedule.

Basic Sort Approximation Algorithm

Sort all students by their age, so we have a sorted array in which all students from [i] are the same age, and all students in [i] are older than all students in [j] for all j <i. Now consider each pair i, j from which there exists O (n ^ 2), where we also have that | Age [i] - Age [j] | <= 2. Find the largest group of students of different nationalities and place them in the room together. We sequentially iterate over pairs of indexes O (n ^ 2), which satisfy a strict restriction and take all students with a difference in nationality (which we can find by preprocessing and hashing on pairs of indexes). By doing this carefully (for example, looking at the indices i j that are scattered before they are close to each other), further improving the runtime. It seems like it should be polytime, but I think there are some subtleties that need to be addressed first before saying this.