Re: Preferable Pairs (#165)

I made a couple of minor optimizations to my solution. It still will
not handle large inputs, but it is a little better. Thanks to Eric
Ivancich, I removed some of the duplicate checks of potential solutions.
I hope I got them all. Also, I added some memoization for values of
solution sets, which has the downside of requiring more memory but seems
to improve overall performance.

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
@pair_set_value_hash =
@pair_value_hash =

#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 looks up the pair value in a hash
#preference indexes, 0=best, 1=next best, etc.
def get_pair_value(pair)
pair_array = pair.split(" ")
return 0 if(pair_array.length==1)

#get the value from the pair value hash
return @pair_value_hash[pair] + @pair_value_hash[pair_array[1] + " " 
  • pair_array[0]]

    #this method calculates the value of a possible solution of pairs
    def get_pair_set_val(pair_set)
    #check the hash first
    return @pair_set_value_hash[pair_set]

    #not in the hash calculate it
    val = 0
    pair_set.each {|next_pair| val += get_pair_value(next_pair)}
    @pair_set_value_hash[pair_set] = val
    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)

      #add to all pairs list
      all_pairs += [p1 + " " + p2] unless(all_pairs.include?(p2 + " " 
  • p1))

      #add to pair_value_hash for later lookup
      @pair_value_hash[p1 + " " + p2] = (cnt-1)**2
    #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

t1 =
pc =“list.yaml”)
pair_set = pc.get_preferred_pairs
pair_set.each {|pair| puts pair}
t2 =
puts “Pair set value: #{pc.get_pair_set_val(pair_set)} \nTime: #{t2 -