# Re: Preferable Pairs (#165) **URL:** \ **Category:** Ruby\ **Created:** [June 8, 2008, 4:55pm UTC](https://www.ruby-forum.com/t/re-preferable-pairs-165/139880 "2008-06-08T16:55:41Z")\ **Posts on this page:** 3\ **Page:** 1
**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\ **Post date:** [June 8, 2008, 4:55pm UTC](https://www.ruby-forum.com/t/re-preferable-pairs-165/139880/1 "2008-06-08T16:55:41Z")
In fact, this _is_ the Stable Roommates problem. ----- Original Message ---- From: Matthew M. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) To: ruby-talk ML [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) Sent: Friday, June 6, 2008 12:43:43 PM Subject: [QUIZ] Preferable Pairs (#165) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- The three rules of Ruby Q. 2: 1. Please do not post any solutions or spoiler discussion for this quiz until 48 hours have passed from the time on this message. 2. Support Ruby Q. 2 by submitting ideas as often as you can! (A permanent, new website is in the works for Ruby Q. 2. Until then, please visit the temporary website at 3. Enjoy! Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone on Ruby T. follow the discussion. Please reply to the original quiz message, if you can. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ## Preferable Pairs (#156) Imagine a pairs tournament: a competition where every player partners up with another for the duration of the tournament. Everyone plays in a pair and wins or loses in a pair. But everyone arrives individually, and only pairs up at the start. Every player has preferences for a partner; your task is to try and optimize those preferences as best as possible. The input is a series of lines containing names, such as: ``` David: Helen Vicki Joseph Helen: David Vicki Joseph Joseph: Vicki Helen David Vicki: David Helen Joseph ``` Each line represents the preferences of the first named player (i.e. before the colon). That player’s preferred parters are listed after the colon, in order of preference (i.e. most preferred first, least preferred last). The output of your code should be the pairings, one pair per line. For the example above, your output should look like this: ``` David Helen Joseph Vicki ``` If an odd number of people were provided at the start, then one person will be left out. That person’s name should be output alone on the last line. What determines the best pairing? A score will be calculated for your output against the input. For each player, the partner is found in the player’s ordered list, as an index. So, for the above example: ``` David: 0 Helen: 0 Joseph: 0 Vicki: 2 ``` Each individual’s score is then squared, then all are added together. Here, the final score is 4. The _lower_ your score, the better the match. ---
**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\ **Post date:** [June 8, 2008, 8:07pm UTC](https://www.ruby-forum.com/t/re-preferable-pairs-165/139880/2 "2008-06-08T20:07:18Z")
> In fact, this _is_ the Stable Roommates problem. Sure looks like it… I probably should have remembered this from university. I wonder if the scoring method I presented is essentially equivalent to the stability condition. ---
**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\ **Post date:** [June 8, 2008, 8:36pm UTC](https://www.ruby-forum.com/t/re-preferable-pairs-165/139880/3 "2008-06-08T20:36:51Z")
On 6/8/08, Matthew M. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > > In fact, this _is_ the Stable Roommates problem. > > Sure looks like it… I probably should have remembered this from > university. I wonder if the scoring method I presented is essentially > equivalent to the stability condition. I don’t think this quiz is equivalent to the “stable roommates problem”. The stable roommates problem just wants a local minimum solution. This may be a reasonable approximation to the problem. I think the “weighted matching problem” is closer to this quiz. This problem looks to be NP-complete.