views:

220

answers:

3

Just a curiosity question. Remember when in class groupwork the professor would divide people up into groups of a certain number (n)?

Some of my professors would take a list of n people one wants to work with and n people one doesn't want to work with from each student, and then magically turn out groups of n where students would be matched up with people they prefer and avoid working with people they don't prefer.

To me this algorithm sounds a lot like a Knapsack problem, but I thought I would ask around about what your approach to this sort of problem would be.

EDIT: Found an ACM article describing something exactly like my question. Read the second paragraph for deja vu.

+1  A: 

This problem can be brute-forced, hence my approach would be first to brute force it, then fix it when I get a better idea.

Lo'oris
Uhh, ok, we know how to brute force it. How is that an answer?
WhirlWind
I think Knuth would agree with you there.
Jweede
@WhirlWind: he didn't ask specifically what algorithm we would have used, he asked "what your approach to this sort of problem would be". And this would be my approach.
Lo'oris
The problem can be brute-forced, yay that means it's computable for sure.
Jacob Schlather
I must have some qubits around here somewhere...
WhirlWind
+4  A: 

To me it sounds more like some sort of clique problem.

The way I see the problem, I'd set up the following graph:

  • Vertices would be the students
  • Two students would be connected by an edge if both of these following things hold:
    1. At least one of the two students wants to work with the other one.
    2. None of the two students doesn't want to work with the other one.

It is then a matter of partitioning the graph into cliques of size n. (Assuming the number of students is divisible by n)

If this was not possible, I'd probably let the first constraint on the edges slip, and have edges between two people as long as neither of them explicitly says that they don't want to work with the other one.

As for an approach to solving this efficiently, I have no idea, but this should hopefully get you closer to some insight into the problem.

Sebastian P.
Interesting... you could probably even use that to figure out the complexity of the problem.
WhirlWind
Graph theory was my other thought about the problem. If I remember right, cliques are NP-Hard. However I don't think class sizes will be so large as to make this intractable.
Jweede
@Jweede, it's actually NP-complete according to that wikipedia article. Which I guess also makes it NP-Hard.
Cam
@incrediman Yep, NP-Complete problems are a subset of NP-Hard problems.
Jweede
+2  A: 

You could model this pretty easily as a clustering problem and you wouldn't even really need to define a space, you could actually just define the distances:

Make two people very close if they both want to work together. Close if one of them wants to work with the other. Medium distance if there's just apathy. Far away if either one doesn't want to work with the other.

Then you could just find clusters, yay. Then split up any clusters of overly large size, with confidence that the people in the clusters would all be fine working together.

Jacob Schlather
The idea is interesting. Using distance in that abstract space allows us not to try and plot the points (which would necessitates solving the problem in the first place). Since partitioning a cluster takes about O(Size) time, I think we could solution the problem fairly efficiently there. One would need to tweak the distance though, to account for symmetry (you should be more likely to work with someone you like and like you than with someone you like but who does not care about you). That means 5 distances instead of 3 if we estimate that Love-Hate is equivalent to Medium-Medium.
Matthieu M.