11

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.

Jon W
  • 15,480
  • 6
  • 37
  • 47
  • 1
    That sounds nice; my professors always assigned me to work with the laziest people in the class and I'd end up doing too much work. ;-) – James McNellis May 16 '10 at 20:26
  • @james sometimes it's the best way to learn. ;) – Jon W May 16 '10 at 20:28
  • 7
    @Jweede: it might be a good way to learn that (1) people will exploit you and (2) you boss won't recognize your hard work – o0'. May 16 '10 at 20:36
  • Your use of `n` is rather ubiquitous. Every student must like and dislike the same number `n` of people? – IVlad May 16 '10 at 20:41
  • @IVlad true. Ideally one would pick 3 people they like, and 3 they dislike. However in practice, `n` is only a maximum. – Jon W May 16 '10 at 20:51
  • @Lo'oris: sadly my college doesn't offer that course explicitly. But I think it's something we all learn one way or another. – Jon W May 16 '10 at 20:58

4 Answers4

5

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 Paaske Tørholm
  • 49,493
  • 11
  • 100
  • 118
  • Interesting... you could probably even use that to figure out the complexity of the problem. – WhirlWind May 16 '10 at 20:50
  • 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. – Jon W May 16 '10 at 20:54
  • @Jweede, it's actually NP-complete according to that wikipedia article. Which I guess also makes it NP-Hard. – Cam May 16 '10 at 21:06
  • @incrediman Yep, NP-Complete problems are a subset of NP-Hard problems. – Jon W May 16 '10 at 21:12
3

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.

JSchlather
  • 1,564
  • 2
  • 13
  • 22
  • 1
    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. May 17 '10 at 18:41
1

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.

o0'.
  • 11,739
  • 19
  • 60
  • 87
0

There are a couple of algorithms you could use. A great example is the so called "stable marriage problem", which has a perfect solution. You can read more about it here:

http://en.wikipedia.org/wiki/Stable_marriage_problem

The stable marriage problem only works with two groups of people (men/women in the marriage case). If you want to form pair you can use a variation, the stable roommate problem. In this case you create pairs but everybody comes from a single pool.

But you asked for a team (which I translate into >2 people per team). In this case you could let everybody fill in their best to worst match and then run the

Roy van Rijn
  • 840
  • 7
  • 17