I am looking for an algorithm that "describes" the following situation:

15 - 22 people are combined into groups of 4 or 5 based upon stated preferences of who they wish to be grouped with. Each person will be grouped with at least one of their preferences.

This isn't "homework".

  • 2
    $\begingroup$ Your problem appears to be the same as the one discussed in stackoverflow.com/questions/294660/… $\endgroup$ – svenkatr Nov 9 '10 at 17:42
  • $\begingroup$ It's not quite the same as either the Stack Overflow problem or the marriage problem. The Stack Overflow problem requires every person in a particular group to be on all the others' preference lists, while this problem requires only at least one. The marriage problem requires ranked preferences, not binary ones. (Note that the accepted Stack Overflow answer also wrongly assumes that this is the marriage problem, as some of the other answers to that question point out.) Some variation of an algorithm to solve one of these other problems might work on this one, or it might not. $\endgroup$ – Mike Spivey Nov 10 '10 at 19:47

This appears to be a variation of the marriage problem. You might want to consider work related to this one.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy