M
Matthew Moss
[Note: parts of this message were removed to make it a legal post.]
Apologies for being a little late today... Took a little bit to understand
some of what was going on in the solutions for the Preferable Pairs quiz,
and I'm not certain I explained it well enough, but... here it is.
This "Preferable Pairs" quiz is, as was noted, very similar to the [Stable
Roommates][1] 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][2] 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`.
[1]: http://en.wikipedia.org/wiki/Stable_roommates_problem
[2]: http://en.wikipedia.org/wiki/Np_complete
Apologies for being a little late today... Took a little bit to understand
some of what was going on in the solutions for the Preferable Pairs quiz,
and I'm not certain I explained it well enough, but... here it is.
This "Preferable Pairs" quiz is, as was noted, very similar to the [Stable
Roommates][1] 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][2] 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`.
[1]: http://en.wikipedia.org/wiki/Stable_roommates_problem
[2]: http://en.wikipedia.org/wiki/Np_complete