ThoML
6/8/2008 6:30:00 PM
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