--_f9242196-38a8-486f-a830-cae6cc4687ca_
Content-Type: text/plain; charset="Windows-1252"
Content-Transfer-Encoding: quoted-printable


 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'tork.  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)}"


_________________________________________________________________
Now you can invite friends from Facebook and other groups to join you on Windows LiveMessenger. Add now.
https://www.invite2messenger.net/im/?source=TXT_EML_WLH_AddNow_Now-_f9242196-38a8-486f-a830-cae6cc4687ca_--