# Re: Preferable Pairs (#165)

**URL:** <https://www.ruby-forum.com/t/re-preferable-pairs-165/139917>\
**Category:** Ruby\
**Created:** [June 9, 2008, 4:27am UTC](https://www.ruby-forum.com/t/re-preferable-pairs-165/139917 "2008-06-09T04:27:07Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![Steven\_Hahn](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/5f8ce5/32.png) [@Steven\_Hahn](https://www.ruby-forum.com/u/Steven_Hahn)\
**Post date:** [June 9, 2008, 4:27am UTC](https://www.ruby-forum.com/t/re-preferable-pairs-165/139917/1 "2008-06-09T04:27:07Z")

</div>

## 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

```

end

#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)  
@pairs\_hash[person].scan(/\w+/)[n]  
end

#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)  
return  
@pairs\_hash[pair\_array[0]].scan(/\w+/).index(pair\_array[1])\*\*2 +  
@pairs\_hash[pair\_array[1]].scan(/\w+/).index(pair\_array[0])\*\*2  
end

#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  
end

#this method calculates a list of pairs from the pair array minus the  
#head\_pair and any similar pairs (see similar? method for more  
details).  
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))  
end  
return tail\_array  
end

#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|
  if(pair2.include?(next_name))
    return true
  end
end
return false

```

end

#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]  
end  
#add individual names if there are an odd number of people  
all\_pairs += [p1] if (@num\_people & 1 == 1)  
end  
return all\_pairs  
end

#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  
if(pair\_array.length==0)  
return solution  
end

```
#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)
  if(solution_value>pair_set_val)
    #better solution has been found... save it!
    solution = pair_set
    solution_value = pair_set_val
  end
end
return solution

```

end  
end

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

pc = PairCalculator.new(ARGV[0])  
pair\_set = pc.get\_preferred\_pairs  
pair\_set.each {|pair| puts pair}  
puts “Pair set value: #{pc.get\_pair\_set\_val(pair\_set)}”