Preferable Pairs (#165)

[mansfiem]

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

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

   http://splatbang.com/rubyquiz/.

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.

[mansfiem]

Here is some quick code to generate sample preferences. Takes a single
optional argument (defaults to 10) which is the number of people to
generate. (I’ve got 34 names in here; if you want to try larger sets,
you’ll have to add more names.)

NAMES = %w(Adam Anna Bob Betty Chuck David Daria Evan Ellen Fred Faye
Greg Gail Hank Helen Irene John Janet Laura Matt Maria Nadine Oleg
Olivia Peter Pamela Ric
k Rosa Steve Susan Theo Tracy Vicki Walter)

def sample(n)
names = NAMES.sort_by { rand }[0, n].sort
names.each do |name|
others = names.dup.reject { |other| other == name }.sort_by
{ rand }
puts “#{name}: #{others.join(’ ')}”
end
end

sample(Integer(ARGV[0] || 10))

[mansfiem]

In addition to the sample generation code, here are some examples with
output produced from the initial version of my solution. I think I
have a good algorithm, but I haven’t proven that it generates the
optimal solution.

Example A input:
Bob: Ellen Evan Vicki Helen Theo David Tracy Daria Matt
Daria: Helen Evan Ellen David Bob Matt Tracy Theo Vicki
David: Helen Matt Bob Daria Vicki Theo Evan Tracy Ellen
Ellen: Bob Daria Helen Evan Matt Theo Tracy Vicki David
Evan: Bob David Tracy Ellen Daria Vicki Helen Matt Theo
Helen: Theo Daria Tracy Bob Evan Matt Vicki David Ellen
Matt: Helen Ellen David Bob Theo Daria Tracy Evan Vicki
Theo: Ellen Bob David Tracy Vicki Helen Matt Daria Evan
Tracy: Evan Daria Bob Matt Ellen Vicki Theo Helen David
Vicki: Tracy Daria Theo Helen Bob Ellen Matt Evan David

Example A output:
Ellen Bob
Daria Helen
Tracy Evan
David Matt
Vicki Theo

Example B input:
David: John Hank Evan Gail Walter
Evan: David Hank Gail Walter John
Gail: David John Walter Evan Hank
Hank: Gail John Walter David Evan
John: Hank David Evan Gail Walter
Walter: Evan John Hank Gail David

Example B output:
David John
Walter Evan
Hank Gail

Example C input:
Anna: Betty Rosa Daria Helen Ellen Theo
Betty: Rosa Daria Anna Helen Theo Ellen
Daria: Rosa Theo Ellen Helen Betty Anna
Ellen: Betty Helen Rosa Daria Theo Anna
Helen: Theo Daria Anna Rosa Ellen Betty
Rosa: Daria Ellen Helen Betty Theo Anna
Theo: Daria Ellen Helen Betty Anna Rosa

Example C output:
Rosa Daria
Betty Anna
Helen Theo
Ellen

[mansfiem]

On Jun 7, 1:23 am, ThoML [email protected] wrote:

Or is the list of preferences always complete, i.e. it always contains
all other players?

Yes, always complete, the least preferred players will be toward the
end.

[mansfiem]

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

What is the penalty for “unwanted” pairings, e.g.

David: Helen Vicki
Helen: David
Joseph: Vicki Helen
Vicki: David

with output:

David Joseph
Helen Vicki

Or is the list of preferences always complete, i.e. it always contains
all other players?

[mansfiem]

On Jun 6, 3:57 pm, Matthew M. [email protected] wrote:

In addition to the sample generation code, here are some examples with
output produced from the initial version of my solution. I think I
have a good algorithm, but I haven’t proven that it generates the
optimal solution.

Walter Evan
Hank Gail

I think that scores 26. A score of 18 is achievable (see below),
although I don’t know if it’s optimal. With only 15 (I think)
potential partnership schemes when there are six people, it could be
verified, although I haven’t done it.

David Evan
Hank John
Gail Walter

By the way, if there are n people, I believe the formula for the
number of partnership schemes is:

n! / (n / 2)! / 2**(n / 2)

Eric

====

LearnRuby.com offers Rails & Ruby HANDS-ON public & ON-SITE
workshops.
Ruby Fundamentals Wkshp June 16-18 Ann Arbor, Mich.
Ready for Rails R. Wkshp June 23-24 Ann Arbor, Mich.
Ruby on Rails Wkshp June 25-27 Ann Arbor, Mich.
Ruby Plus Rails Combo Wkshp June 23-27 Ann Arbor, Mich
Please visit http://LearnRuby.com for all the details.

[mansfiem]

David Evan
Hank John
Gail Walter

Correct you are, sir. My algorithm is greedy, but after a certain
transform was done, which I had hoped would make greedy acceptable. I
guess not.

Back to the drawing board…

[mansfiem]

I used a genetic algorithm that tries to find the best solution
possible in a given number of iterations. It doesn’t always find the
best, but generally does pretty well. And because there are
randomized aspects to each run, you can end up with different
solutions (of different scores) on consecutive runs. The code can be
found at:

http://learnruby.com/examples/ruby-quiz-165.shtml

Eric

====

LearnRuby.com offers Rails & Ruby HANDS-ON public & ON-SITE
workshops.
Ruby Fundamentals Wkshp June 16-18 Ann Arbor, Mich.
Ready for Rails R. Wkshp June 23-24 Ann Arbor, Mich.
Ruby on Rails Wkshp June 25-27 Ann Arbor, Mich.
Ruby Plus Rails Combo Wkshp June 23-27 Ann Arbor, Mich
Please visit http://LearnRuby.com for all the details.

[mansfiem]

Stable roommates or not, I have two solutions. The second one is
supposed to be exact. No fancy genetic batteries included.

Regards,
Thomas.

======================================================== #1
#!/usr/bin/env ruby19

def read_names(file)
data = {}
File.readlines(file).each do |l|
next if /^\s*%/ =~ l
name, *prefs = l.scan(/[^:[:space:]]+/)
data[name] = prefs if name
end
return data
end

def match_names(data)
names = data.keys

# sort pairings
mt = Hash.new {|h, k| h[k] = []}
names.each do |k|
    data[k].each_with_index do |l, v|
        mt[v ** 2 + data[l].index(k) ** 2] << [k, l]
    end
end

# collect pairs
pairs = []
catch(:exit) do
    mt.entries.sort.each do |pri, opairs|
        opairs.each do |ab|
            if ab.all? {|n| names.include?(n)}
                pairs << ab
                names -= ab
                throw :exit if names.size < 2
            end
        end
    end
end

# add remaining singles
pairs << names unless names.empty?

return pairs

end

if FILE == $0
data = read_names(ARGV[0])
pairs = match_names(data)
puts pairs.map {|e| e.join(" “)}.join(”\n")

if $DEBUG
    def assess(data, pairs)
        pairs.inject(0) do |s, e|
            a, b = e
            if a and b
                va = data[a].index(b) ** 2
                vb = data[b].index(a) ** 2
                s + va + vb
            else
                s
            end
        end
    end
    puts assess(data, pairs)
end

end

======================================================== #2
#!/usr/bin/env ruby19

def read_names(file)
data = {}
File.readlines(file).each do |l|
next if /^\s*%/ =~ l
name, *prefs = l.scan(/[^:[:space:]]+/)
data[name] = prefs if name
end
return data
end

def optimize(data, pairings, names, range, pairs=[], weight=0,
maxweight=nil)
bestpairs = nil
maxweight ||= pairings.keys.max ** 2 + 1
for pos in range
weight1 = weight + pos
break if weight1 >= maxweight
pairings[pos].each do |pair|
if names & pair == pair
pairings[pos].delete(pair)
pairs << pair
begin
names1 = names - pair
if names1.size < 2
bestpairs = pairs.dup
bestpairs << names1 unless names1.empty?
return [weight1, bestpairs]
elsif pos < maxweight - weight1
w1, p1 = optimize(data, pairings, names1,
pos…range.max, pairs, weight1, maxweight)
if p1 and w1 < maxweight
maxweight = w1
bestpairs = p1
end
end
ensure
pairs.pop
pairings[pos].unshift(pair)
end
end
end
end
return [maxweight, bestpairs]
end

def match_names(data)
names = data.keys

# sort pairings
pairings = Hash.new {|h, k| h[k] = []}
maxpos = 0
names.each do |k|
    data[k].each_with_index do |l, v|
        w = v ** 2 + data[l].index(k) ** 2
        maxpos = w if w > maxpos
        pairings[w] << [k, l]
    end
end

# collect pairs
weight, pairs = optimize(data, pairings, names, 0..maxpos)

return pairs

end

def assess(data, pairs)
pairs.inject(0) {|s, e| s + assess_pair(data, e)}
end

def assess_pair(data, pair)
a, b = pair
if a and b
va = data[a].index(b) ** 2
vb = data[b].index(a) ** 2
va + vb
else
0
end
end

if FILE == $0
data = read_names(ARGV[0])
pairs = match_names(data)
puts pairs.map {|e| e.join(" “)}.join(”\n")
puts assess(data, pairs) if $DEBUG
end

[mansfiem]

Here’s my solution - I think I’ve got it, but haven’t found a way to
prove whether or not it’s optimal yet

-Dustin

parse input file

make a hash, key is player, value is array of preferred matches

in order of preference

preferences = {}
File.open(ARGV[0]) do |file|
while line = file.gets
a = line.split
player = a[0][0…a[0].size-1]
preferences[player] = a[1…a.size]
end
end

score each individual preference, first choice gets 0 score

i.e. lower scores are better

keys = preferences.keys

matrix = keys.collect { |k| Array.new }
keys.each_with_index do |player, i|
keys.each_with_index do |oplayer, j|
next if j < i + 1 # process above main diagonal
# storing score, which is position of oplayer in preference list
s1 = preferences[player].index(oplayer)
s2 = preferences[oplayer].index(player)
score = s1 + s2
entry = [player, oplayer, score]
matrix[i].push(entry)
matrix[j].push(entry)
end
end

matrix.size.times do |i|
matrix[i] = matrix[i].sort { |a,b| a[2] <=> b[2] }
end

matches = []

(matrix.size - 2).downto(1) do |i|
matrix = matrix.sort { |a,b| b[i][2] <=> a[i][2] }
end

while matrix.size > 0
matrix = matrix.sort { |a,b| a[0][2] <=> b[0][2] }

match = matrix.first.first
matches.push([match[0], match[1]])

matrix.size.times do |i|
matrix[i].delete_if do |pmatch|
pmatch.include?(match[0]) || pmatch.include?(match[1])
end
end
matrix.delete_if { |row| row.empty? }

end

matches.each do |match|
puts “#{match[0]} #{match[1]}”
end

find the odd one…

puts keys - matches.flatten.uniq

[mansfiem]

On Jun 7, 11:05 pm, “Eric I.” [email protected] wrote:

By the way, if there are n people, I believe the formula for the
number of partnership schemes is:

n! / (n / 2)! / 2**(n / 2)

An alternative (and more efficient) way to compute the number of
partnership schemes is to multiply all the odd values from 1…n. For
example, if there are eight people, then we have 1 * 3 * 5 * 7, or
105.

Eric

====

LearnRuby.com offers Rails & Ruby HANDS-ON public & ON-SITE
workshops.
Ruby Fundamentals Wkshp June 16-18 Ann Arbor, Mich.
Ready for Rails R. Wkshp June 23-24 Ann Arbor, Mich.
Ruby on Rails Wkshp June 25-27 Ann Arbor, Mich.
Ruby Plus Rails Combo Wkshp June 23-27 Ann Arbor, Mich
Please visithttp://LearnRuby.comfor all the details.

[mansfiem]

I have a solution at the end of this message. This solution finds the
optimal solution. I believe this problem is NP-complete, so a fast
optimal
solution for large inputs is out of the question. But, there are some
things that I did that give significant performance improvement:

• Used memoization to not recalculate costs for subsets that have
  already
  been computed. This reduced the complexity from O(n!) to O(2**n).

• Divided finding the pairs into 2 phases: finding min cost, and finding
  pairs based on min costs. This simplified the bottleneck of finding the
  min
  cost and reduced its overhead. Given the min costs, the pairs can be
  found
  in O(n**2).

• Mapped each player to a bit index/mask. This allowed a set of players
  to
  be represented as simply an Integer/Fixnum.

• Applied some O(1) bit-searching techniques I developed about 10 years
  ago
  on the hardware side (x86 BSR - bit-scan-reverse).

• No small objects are created (and garbage collected) during the
  algorithm.

Eric

#!/usr/bin/env ruby

Infinity = 1.0/0.0

class PreferrablePairs

def initialize
    # remaining bit pattern => cost (init to no remaining => 0)
    # size will be O(2**n)
    # only patterns with an even number of bits set will be used
    @cost = [0]
    #@cost = {0=>0} # Hash could be used just as well (little 

slower)
@mask = 1 # next mask to use
# mask <=> name maps
@mask2name = {}
@name2mask = Hash.new { |name2mask, name|
# create a new entry when it is missing
begin
@mask2name[@mask] = name
name2mask[name] = @mask
ensure
# post operation
@mask <<= 1
end
}
end

# throw out all cached costs - for more than just pairs
# O(2**n)
def flush
    @mask.times { |rem|
        # little trick for masking lowest bit set (applied twice)
        rem2 = rem&(rem-1)
        rem2 = rem2&(rem2-1)
        next if rem2.zero? # 2 or fewer bits of mask set
        @cost[rem] = nil
    }
end

# add a cost between a pair
def add(first, second, cost)
    mask = @name2mask[first]|@name2mask[second]
    @cost[mask] = (@cost[mask]||0)+cost
end

# fill-in default costs for unassociated pairs
# ensure we have an even number of entries
def fill(defcost=0, evenname="", evencost=0)
    mask1 = 1
    while mask1<@mask
        mask2 = mask1<<1
        while mask2<@mask
            @cost[mask1|mask2] ||= defcost
            mask2 <<= 1
        end
        mask1 <<= 1
    end
    if (@name2mask.size&1).nonzero?
        # add another entry when we have an odd number
        mask2 = @name2mask[evenname]
        mask1 = 1
        while mask1<@mask
            @cost[mask1|mask2] ||= evencost
            mask1 <<= 1
        end
    end
end

# cost for a remaining set of entries
# O(2**n) if @cost is not cached (n=remaining entries)
# O(n**2) if @cost is cached
# O(n!+) if memoization is disabled
def cost(remaining=@mask-1)
    bestcost = Infinity
    # iterate through all pairs in remaining
    mask1 = 1
    # little trick find the next set bit from mask1
    while (mask1 = remaining&~(remaining-mask1)).nonzero?
        rem1 = remaining&~mask1 # remove first from remaining
        mask2 = mask1
        while (mask2 = rem1&~(rem1-mask2)).nonzero?
            rem2 = rem1&~mask2 # remove second from remaining
            # cost is for this pair + cost of remaining pairs
            # ||= does memoization for us (change to || to not do 

it)
cost = @cost[mask1|mask2] + (@cost[rem2]||=cost(rem2))
# keep the min cost
if cost<bestcost
bestcost = cost
end
mask2 <<= 1
end
mask1 <<= 1
end
bestcost
end

# pair the entries up
# needs to know what the best cost is first
# yields each pair
# O(n**2) w/ memoization
# O(n!+) w/o memoization
def pair(bestcost, remaining=@mask-1) # :yield: first, second
    while (mask1 = remaining&~(remaining-1)).nonzero?
        rem1 = remaining&~mask1
        mask2 = mask1
        while (mask2 = rem1&~(rem1-mask2)).nonzero?
            # @cost[...] => (@cost[...]||cost(...)) to skip 

memoization
if
(cost0=@cost[mask0=mask1|mask2])+@cost[rem1&~mask2]==bestcost
# yield a best pairings
yield(@mask2name[mask1], @mask2name[mask2])
bestcost -= cost0
remaining &= ~mask0
break
end
mask2 <<= 1
end
end
end

end

require ‘strscan’

preferrable = PreferrablePairs.new
scanner = StringScanner.new("")

STDIN.each_line { |line|
scanner.string = line
scanner.scan(/\s*/)
first = scanner.scan(/\w+/) or next
scanner.scan(/\s*:/) or next
order = 0
while scanner.scan(/\s*/) and second = scanner.scan(/\w+/)
preferrable.add(first, second, order*order)
order += 1
end
}
preferrable.fill

require ‘benchmark’

pairs = nil
cost = nil

4.times {
Benchmark.bm { |b|
pairs = “”
b.report {
cost = preferrable.cost
preferrable.pair(cost) { |first, second|
pairs.concat("#{first} #{second}\n")
}
}
preferrable.flush
}
}

STDERR.puts(cost)
puts(pairs)

[mansfiem]

On 6/8/08, Eric M. [email protected] wrote:

pairs based on min costs. This simplified the bottleneck of finding the

• No small objects are created (and garbage collected) during the
  algorithm.

I improved on this solution further:

• The outer loop in #cost was unnecessary. I believe the complexity
  before
  was actually O(nn2n) and now it should be O(n*2n).

• Used Hash instead of Array for costs. Not sure why this helped (Array
  was
  faster in previous solution).

The new solution is below. My previous solution could only reasonably
handle about 16 players and the new solution handles about 26 players.

Eric

#!/usr/bin/env ruby

Infinity = 1.0/0.0

class PreferrablePairs

def initialize
    # remaining bit pattern => cost (init to no remaining => 0)
    # size will be O(2**n)
    # only patterns with an even number of bits set will be used
    #@cost = [0] # Array
    @cost = {0=>0} # Hash seems faster and takes less memory
    @mask = 1 # next mask to use
    # mask <=> name maps
    @mask2name = {}
    @name2mask = Hash.new { |name2mask, name|
        # create a new player when it is missing
        begin
            @mask2name[@mask] = name
            name2mask[name] = @mask
        ensure
            # post operation
            @mask <<= 1
        end
    }
end

# throw out all cached costs - for more than just pairs
# O(2**n)
def flush
    if @cost.respond_to?(:map!)
        # Array
        rem = -1
        @cost.map! { |cost|
            rem += 1
            cost ? (((rem2=rem&(rem-1))&(rem2-1)).zero? ? cost : 

nil) :
nil
}
else
# Hash
@cost.delete_if { |rem, cost|
((rem2=rem&(rem-1))&(rem2-1)).nonzero?
}
end
end

# add a cost between a pair
def add(first, second, cost)
    mask = @name2mask[first]|@name2mask[second]
    @cost[mask] = (@cost[mask]||0)+cost
end

# ensure we have an even number of players
def even(name="", cost=0)
    if (@name2mask.size&1).nonzero?
        # add another player when we have an odd number
        mask2 = @name2mask[name]
        mask1 = 1
        while mask1<@mask
            @cost[mask1|mask2] ||= cost
            mask1 <<= 1
        end
    end
end

# fill-in default costs for unassociated pairs
def fill(defcost=0, evenname="", evencost=0)
    mask1 = 1
    while mask1<@mask
        mask2 = mask1<<1
        while mask2<@mask
            @cost[mask1|mask2] ||= defcost
            mask2 <<= 1
        end
        mask1 <<= 1
    end
end

# cost for a remaining set of players
# O(n*2**n) if @cost is not cached (n=remaining players)
# O(n) if @cost is cached
def cost(remaining=@mask-1)
    bestcost = Infinity
    # arbitrarily pick lowest remaining bit to pair
    mask1 = remaining&~(remaining-1)
    rem1 = remaining^mask1 # remove first from remaining
    mask2 = mask1
    # little trick find the next set bit from rem1
    while (mask2 = remaining&~(remaining-(mask2<<1))).nonzero?
        # cost is for this pair + cost of remaining pairs
        cost = @cost[mask1|mask2] + 

(@cost[rem2=rem1^mask2]||cost(rem2))
# keep the min cost
bestcost = cost if cost<bestcost
end
@cost[remaining] = bestcost
end

# pair the players up
# cost should have been calculated already
# yields each pair
# O(n**2)
def pair(remaining=@mask-1) # :yield: first, second
    bestcost = @cost[remaining]
    while (mask1 = remaining&~(remaining-1)).nonzero?
        mask2 = mask1
        begin
            mask2 = remaining&~(remaining-(mask2<<1))
        end until

(cost0=@cost[mask0=mask1|mask2])+@cost[remaining^mask0]==bestcost
# yield a best pairings
yield(@mask2name[mask1], @mask2name[mask2])
bestcost -= cost0
remaining ^= mask0
end
end

end

require ‘strscan’

preferrable = PreferrablePairs.new
scanner = StringScanner.new(“”)

STDIN.each_line { |line|
scanner.string = line
scanner.scan(/\s*/)
first = scanner.scan(/\w+/) or next
scanner.scan(/\s*:/) or next
order = 0
while scanner.scan(/\s*/) and second = scanner.scan(/\w+/)
preferrable.add(first, second, order*order)
order += 1
end
}
preferrable.even
preferrable.fill # just in case some pairs are missing

require ‘benchmark’

pairs = nil
cost = nil

2.times {
Benchmark.bm { |b|
pairs = “”
b.report {
cost = preferrable.cost
preferrable.pair { |first, second|
pairs.concat(“#{first} #{second}\n”)
}
}
preferrable.flush
}
}

STDERR.puts(cost)
puts(pairs)

[mansfiem]

pairings[pos].delete(pair)
[…]
pairings[pos].unshift(pair)

I just realized that this behaves differently in ruby18 and ruby19
when used within an each loop. These lines could be removed.

Also, my submission generates too many pairs. The following sorts the
pairs so that a perfect match is included only once.

names.each do |k|
    data[k].each_with_index do |l, v|
        w = v ** 2 + data[l].index(k) ** 2
        maxpos = w if w > maxpos
        pair = [k, l].sort
        pairings[w] << pair unless pairings[w].include?(pair)
    end
end

In any case, my mostly naive approach lags far behind Eric M and Eric
I’s solutions (which I find quite interesting BTW).

[mansfiem]

Hi folks,

I’m terribly sorry for these repeated posts but I didn’t like the
runtime behaviour of my second solution (especially in comparison to
Eric M.'s submission).

Here is a slightly modified version that makes cuts slightly earlier.
Up to 25 players appear acceptable on my laptop: 22 secs for 20 random
sets of 25 player each.

Regards,
Thomas.

#!/usr/bin/env ruby

def read_names(file)
data = {}
File.readlines(file).each do |l|
next if /^\s*%/ =~ l
name, *prefs = l.scan(/[^:[:space:]]+/)
data[name] = prefs if name
end
return data
end

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

def match_names(data)
names = data.keys.sort

# sort pairings
pairings = Hash.new {|h, k| h[k] = []}
maxpos = 0
names.each do |k|
    data[k].each_with_index do |l, v|
        w = v ** 2 + data[l].index(k) ** 2
        maxpos = w if w > maxpos
        pair = [k, l].sort
        pairings[w] << pair unless pairings[w].include?(pair)
    end
end
pairings1 = []
pairings.each do |pri, pairs|
    pairings1.concat(pairs.zip([pri] * pairs.size))
end
pairings1 = pairings1.sort_by {|a, b| b}

# collect pairs
weight, pairs = optimize(pairings1, names, 0, pairings1.size)

return pairs

end

def assess(data, pairs)
pairs.inject(0) {|s, e| s + assess_pair(data, e)}
end

def assess_pair(data, pair)
a, b = pair
if a and b
va = data[a].index(b) ** 2
vb = data[b].index(a) ** 2
va + vb
else
0
end
end

if FILE == $0
data = read_names(ARGV[0])
pairs = match_names(data)
puts pairs.map {|e| e.join(" “)}.join(”\n")
puts assess(data, pairs) if $DEBUG
end

[mansfiem]

Matthew M. ha scritto:

Imagine a pairs tournament: a competition where every player partners up
Helen: David Vicki Joseph
David Helen
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

[mansfiem]

Andrea F. ha scritto:

please visit the temporary website at

The input is a series of lines containing names, such as:
order of preference (i.e. most preferred first, least preferred last).
be left out. That person’s name should be output alone on the last line.

A ↔ D - score: 1
E ↔ C - score: 25

A ↔ E - score: 8

a scheme (a possible solution) traversing the set of all pairs

Total score: 6

Thanks for the quiz.
Andrea

I improved a bit the comment of my code:

http://pastie.org/212209

Andrea