Andrea Fazzi ha scritto:
> Matthew Moss ha scritto:
>> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>>
>> 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/rubyquiz/>.
>>
>> 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.
>>
>>   
>
> Hi all,
>
> this procedure *doesn't* find the *best* solution. Instead, it aims
> to give *good* results in an acceptable time.
>
> Here the pasties:
>
> http://pastie.org/212099
> http://pastie.org/212100 (specs)
>
> = Description of the algorithm
>
> 1. Find all possible pairs
>
> Given the following preferences matrix:
>
> A: C D E F B
> B: A C D F E
> C: B A F E D
> D: A B E F C
> E: F D A B C
> F: A B E D C
>
> the first step is to find all possible pairs:
>
> A <-> C - score: 1
> A <-> D - score: 1
> A <-> E - score: 8
> A <-> F - score: 9
> A <-> B - score: 16
> B <-> C - score: 1
> B <-> D - score: 5
> B <-> E - score: 25
> B <-> F - score: 10
> F <-> C - score: 20
> F <-> D - score: 18
> F <-> E - score: 4
> E <-> C - score: 25
> E <-> D - score: 5
> D <-> C - score: 32
>
> The score of a pair is given by:
>
> score of pair = score of first player + score of second player
>
> For example, the score of AC pair ( |AC| ) is given by:
>
> |AC| = 0 + 1 = 1
>
> 2. Sort pairs by score
>
> Then the pairs are sorted by score:
>
> A <-> C - score: 1
> A <-> D - score: 1
> B <-> C - score: 1
> F <-> E - score: 4
> E <-> D - score: 5
> B <-> D - score: 5
> A <-> E - score: 8
> A <-> F - score: 9
> B <-> F - score: 10
> A <-> B - score: 16
> F <-> D - score: 18
> F <-> C - score: 20
> E <-> C - score: 25
> B <-> E - score: 25
> D <-> C - score: 32
>
> 3. Select a subset of pairs
>
> A subset of the "best" pairings is then chosen:
>
> A <-> C - score: 1
> A <-> D - score: 1
> B <-> C - score: 1
> F <-> E - score: 4
>
> 4. For each pair produce a scheme
>
> Now, for each pair in the subset at point 3, the algorithm produces
> a scheme (a possible solution) traversing the set of all pairs
> sorted by score.
>
> For example:
>
> given the pair AC taken from the "best" pairings subset, traversing
> the set of all the pairs sorted by score we obtain the scheme below:
>
> A <-> C
> F <-> E
> B <-> D
>
> In this example, four schemes will be produced.
>
> 5. Take the best scheme produced
>
> Finally, to give the "best" result, the procedure takes the scheme
> with minimum score. In this case:
>
> A <-> D - score: 1
> B <-> C - score: 1
> F <-> E - score: 4
>
> Total score: 6
>
> Thanks for the quiz.
> Andrea
>
>

I improved a bit the comment of my code:

http://pastie.org/212209

Andrea