165 Preferable Pairs

Description

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

Summary

This “Preferable Pairs” quiz is, as was noted, very similar to the Stable Roommates problem, though the goal as originally stated is slightly different from the typical presentation of the Stable Roommates problem. Still, the minor goal difference does not change that this is an NP-complete problem, and as such, large input sets would require some sort of approximation, heuristics or other techniques to keep the run time reasonable.

Fortunately, I had no intention of testing the solutions provided on large sets. My test involved a set of 20 people, to be grouped into 10 pairs according to their preferences. Here are the results of my test on the solutions provided.

Solution          Time      Score
Andrea Fazzi      0.159     438
Dustin Barker     0.020     589
Eric Ivancich     4.671     311
Steven Hahn       -DNF-
Eric Mahurin      0.211     311
Matthew Moss      0.022     589
Thomas ML         0.114     311

I neglected to post my own solution, but it’s nearly identical to Dustin’s both in algorithm, results and performance (but mine is much uglier). Also, apologies to Steven… I tried to wait, really I did, but it just kept going, and going…

Andrea, Dustin and myself made straightforward attempts that were fast but not optimal. While the numbers presented above don’t show a huge disparity in performance, I suspect that would be a different story if we were attempting to solve larger datasets, of thousands of people as opposed to twenty. For the tested dataset, I believe there might be a few grumbling people, forced to play with someone they didn’t like very much, but the tournament would go on.

Eric Ivancich provided a genetic algorithm that is notably slower (at this sample size), and isn’t guaranteed to get the most optimal answer, but it happened to do so here. It would be interesting to compare its performance against the optimal solution algorithms for larger data sets.

Eric Mahurin and Thomas ML provided algorithms that find the optimal solution. There is a fair bit of setup code in both to get the data into a convenient form for the optimization algorithm to work. I’m going to skip over that and jump right into Thomas’ optimize method. As input to optimize, the pairings argument looks like this for the sample data:

[
  [["David", "Helen"], 0],
  [["David", "Vicki"], 1],
  [["Helen", "Vicki"], 2],
  [["Joseph", "Vicki"], 4],
  [["Helen", "Joseph"], 5],
  [["David", "Joseph"], 8]
]

Basically, the input is an ordered list of all pairs with the corresponding score (as calculated according to the metric as described by the quiz). It is a combined score, and reflects the preferences of both people in the pair. For example, the pair of Helen and Joseph has a score of 5, because Helen scores Joseph as 4, while Joseph scores Helen as 1: so, 4 + 1 == 5.

Before we conquer the whole of the algorithm, let’s look at a simplified version of optimize to get a feel for the general structure. The input here (for argument pairings) is similar to the above, but without the scores.

def optimize(pairings, names, pos, posmax)
    bestpairs = nil
    while pos < posmax
        pair = pairings[pos]
        pos += 1
        if names & pair == pair
            names1 = names - pair
            if names1.size < 2
                bestpairs = [pair]
                bestpairs << names1 unless names1.empty?
                return bestpairs
            elsif (rv = optimize(pairings, names1, pos, posmax)
                bestpairs = rv
                bestpairs << pair
            end
        end
    end
    return bestpairs
end

bestpairs starts off empty, but by the end should be an array of pairs chosen as the solution. Each iteration of the loop grabs the next pair from pairings and checks to see if it is still usable by set intersection:

        if names & pair == pair

names will contain the names of people still available; that is, those that have not already been chosen previously. The & operator treats the two arrays as sets and performs set intersections. If the result of intersection is equal to one of the arguments, that argument must be a subset of the other, and in this context, is safe to choose for the solution.

When a pair is chosen, those names are removed by Array difference (not quite the same as set difference, but close enough for this case). So it is with:

          names1 = names - pair

That we remove the chosen pair from the list of remaining people. If that is the last possible pair to be made (there are fewer than 2 names remaining), we finish up by setting and returning the bestpairs array

                bestpairs = [pair]
                bestpairs << names1 unless names1.empty?
                return bestpairs

In the case that there is at least one more pair remaining, we continue onto the recursive part of this solution:

            elsif (rv = optimize(pairings, names1, pos, posmax)
                bestpairs = rv
                bestpairs << pair

We know that bestpairs, as returned by the recursive call to optimize, contains the best pairs from the subset of names1, which we got above after removing pair. So we make sure to concatenate pair onto bestpairs before it is returned to the caller.

As simplified, this amounts to a greedy algorithm, since the pairs were initially sorted according to score, and the simplified algorithm, at each level, simply takes the first pair possible.

Now let’s go back to the complete optimize method.

def optimize(pairings, names, pos, posmax, maxweight=nil)
    bestpairs = nil
    maxweight ||= pairings.size ** 2 + 1
    while pos < posmax
        pair, weight1 = pairings[pos]
        break unless weight1 * (names.size / 2).floor < maxweight
        pos += 1
        if names & pair == pair
            names1 = names - pair
            if names1.size < 2
                bestpairs = [pair]
                bestpairs << names1 unless names1.empty?
                return [weight1, bestpairs]
            elsif (rv = optimize(pairings, names1, pos, posmax, maxweight - weight1))
                maxweight, bestpairs = rv
                maxweight += weight1
                bestpairs << pair
            end
        end
    end
    return bestpairs && [maxweight, bestpairs]
end

The algorithm structure is basically the same: recursive, greedily selecting pairs and removing those names from the set of names available… The major difference here is the inclusion of the weights (i.e. scores) and possible rejection of pairs with respect to those weights.

As recursive calls to optimize are made, the maxweight value is updated via this code:

                maxweight, bestpairs = rv
                maxweight += weight1

and checked via this code:

        break unless weight1 * (names.size / 2).floor < maxweight

So a pair may be skipped if it’s weight (scaled by the number of names) exceeds the current maxweight, determined the the current set of choices.

When a possible solution is found, the maxweight variable represents the total score for that solution. But the algorithm does not stop immediately; it keeps checking pairs and solutions of pairs, rejecting those solutions and partial solutions whose total score (i.e. maxweight) would exceed that previously known maxweight.

In the end, the solution reported is the collection of pairs with the lowest total score, and is returned via the original invocation of optimize.


Wednesday, February 04, 2009