[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Re: [QUIZ] Preferable Pairs (#165

James Koppel

6/8/2008 2:54:00 PM

[Note: parts of this message were removed to make it a legal post.]

In fact, this *is* the Stable Roommates problem.


----- Original Message ----
From: Matthew Moss <matthew.moss@gmail.com>
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Sent: Friday, June 6, 2008 12:43:43 PM
Subject: [QUIZ] Preferable Pairs (#165)

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Quiz 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 Quiz 2 by submitting ideas as often as you can! (A
permanent, new website is in the works for Ruby Quiz 2. Until then,
please visit the temporary website at

<http://splatbang.com/rub....

3. Enjoy!
Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby Talk 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.

--
Matthew Moss <matthew.moss@gmail.com>
2 Answers

Matthew Moss

6/8/2008 6:05:00 PM

0

> 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.

Eric Mahurin

6/8/2008 6:34:00 PM

0

[Note: parts of this message were removed to make it a legal post.]

On 6/8/08, Matthew Moss <matthew.moss@gmail.com> 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.