Re: Preferable Pairs (#165)

Ok, I think this one will always find the optimal solution, because it
is exhaustive. Some people were saying that this is the Stable
Roommates problem; I am not familiar with that, but a greedy solution
definitely wouldn’t work. Also, I agree that this does seem like it is
NP-Complete, because greedy does not work and there are O(n!) potential
solutions… I believe (n-1)!! to be exact. I didn’t put in much in the
way of optimizations, so it should not handle a large set of input date.
Since, the input is already YAML-ready, the following program expects
the input to be a YAML file name.

require ‘yaml’

#execute program by providing a file name with the data in YAML format

#Example YAML file contents:

#David: Helen Vicki Joseph

#Helen: David Vicki Joseph

#Joseph: Vicki Helen David

#Vicki: David Helen Joseph

class PairCalculator
def initialize(filename)
#read data into hash from YAML file
@pairs_hash = YAML::load_file(filename)
@num_people = @pairs_hash.length
@num_choices = @num_people - 1

#build array of all possible pairs
@all_pairs = get_all_pairs


#finds the nth choice of a person for some value n, 0 would be
#the first choice, 1 second, etc.
def get_nth_choice(person, n)

#this method returns 0 if the pair is only one name
#otherwise it calculates the sum of the squares of the individual
#preference indexes, 0=best, 1=next best, etc.
def get_pair_value(pair)
pair_array = pair.split(" ")
return 0 if(pair_array.length==1)
@pairs_hash[pair_array[0]].scan(/\w+/).index(pair_array[1])**2 +

#this method calculates the value of a possible solution of pairs
def get_pair_set_val(pair_set)
val = 0
pair_set.each {|next_pair| val += get_pair_value(next_pair)}
return val

#this method calculates a list of pairs from the pair array minus the
#head_pair and any similar pairs (see similar? method for more
def get_tail(pair_array, head_pair)
tail_array = []
pair_array.each do |next_pair|
#remove all pairs with common partners
tail_array += [next_pair] unless(similar?(head_pair, next_pair))
return tail_array

#pairs are considered similar if they share a common name or they
#are both a single name (this case makes sure that only one single
#name can be selected in any given solution
def similar?(pair1, pair2)
#returns true if they are both length of 1
return true if(pair1.split(" “).length==1 and
pair2.split(” ").length==1)

#returns true if the pairs have common partners
pair1.split(" ").each do |next_name|
    return true
return false


#this method generates a list of all possible pairs
def get_all_pairs
all_pairs = []
@pairs_hash.each_key do |p1|
1.upto(@num_choices) do |cnt|
#select the next person in the list
p2 = get_nth_choice(p1, cnt-1)
all_pairs += [p1 + " " + p2]
#add individual names if there are an odd number of people
all_pairs += [p1] if (@num_people & 1 == 1)
return all_pairs

#this method executes an exhaustive search of all pair sets for
#each set it calculates the value with the best found up to that
#point. if the value is lower then it saves the new solution.
def get_preferred_pairs(pair_array=@all_pairs)
solution = []
solution_value = 1.0/0.0
#base case: pair_array is empty
return solution

#iterate over all pairs in the array use each one as the head
#in a potential solution
pair_array.each do |pair|
  #get the next potential solution
  pair_set = [pair] +
    get_preferred_pairs(get_tail(pair_array, pair)) #recursive call
  #calculate the value of the next potential solution
  pair_set_val = get_pair_set_val(pair_set)
    #better solution has been found... save it!
    solution = pair_set
    solution_value = pair_set_val
return solution


if(ARGV.length == 0)
puts “Usage: provide YAML file name as the argument.”
exit 0

pc =[0])
pair_set = pc.get_preferred_pairs
pair_set.each {|pair| puts pair}
puts “Pair set value: #{pc.get_pair_set_val(pair_set)}”