1
$\begingroup$

I am trying to make a system that will sort a list individuals and their preferred list of others. This may not make complete sense, but bear with me.

I have a list of people, each with their list of other people in the main list. The idea is to group the people in to g number of groups, with n number of people per group, while optimizing based on preferences for other people. If one person's preferences request a different person, the algorithm would have to weight the groups so that they are paired together (if possible). If two individuals request each other, it would need to weight that higher than if it was just one way.

I have been puzzling over this for a while, and am hoping that someone here can help find a solution to this, as I am stumped. If it makes any difference, I am developing this in JavaScript.

Does anyone have any ideas on an algorithm to determine the optimal groupings? Pseudo-code, English description or sample code would all be very helpful.

$\endgroup$
1
$\begingroup$

You're probably looking for algorithms to solve the Stable Marriage Problem, also called the Stable Matching Problem, for which many algorithms and implementations are available, depending on the particular problem variant.

$\endgroup$
5
  • $\begingroup$ Wow, that's pretty much exactly what I was looking for. I went to the Wikipedia page for the Stable Marriage Problem, and from there found a link to the Stable Roommate Problem, which is the same except it has one group instead of two. Although I may be able to just implement it as-is, the SRP involves rating the rest of the group. Is there any way that I can modify this so that instead of rating them, I just use the top x choices (Boolean values instead of a rating system)? $\endgroup$ – Wasabi Fan Sep 19 '13 at 6:42
  • $\begingroup$ I think each person needs to provide ranked preferences, and Boolean values won't suffice. Given that it's possible that no stable pairings exist for some instances of the Stable Roommate Problem, the algorithm is probably less likely to return a stable pairing if you provide incomplete preference rankings. $\endgroup$ – Geoff Oxberry Sep 19 '13 at 6:51
  • $\begingroup$ Ok, then here's another question: With the number of people that I have, I wouldn't be able to have everyone rank everyone else. Is there a way to take in only their top x ranked and than apply the algorithm to that? As a side note, I am a programmer and aren't very good at understanding complex algorithms (unfortunately). I have been searching, but can't seem to find any sort of information on this algorithm that makes sense to me. Do you know of a page that explains it in a way that I might understand? $\endgroup$ – Wasabi Fan Sep 19 '13 at 14:08
  • $\begingroup$ I have no idea. It's probably a better question for Computer Science Stack Exchange or Stack Overflow. If you want me to migrate the question to one of those sites, I can. $\endgroup$ – Geoff Oxberry Sep 19 '13 at 18:47
  • $\begingroup$ That would be great! If you can, can you move this to whatever forum you think would be appropriate? I think this has changed from an algorithm question to a programming question... $\endgroup$ – Wasabi Fan Sep 19 '13 at 18:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.