From: Ken Bloom <kbloom@...>
Date: 2007-05-07T00:10:05+09:00
Subject: Re: Unofficial Ruby Quiz -- Ranking Choices

On Thu, 03 May 2007 18:49:09 -0500, Ken Bloom wrote:

> Apparently some people around here can't stand Ruby Quiz withdrawal. For
> those people, here's a quiz question I just came up with.
> 
> I have a list of some items, and I would like to manually rank which
> ones are most important to me. But it's not easy to rank them when I'm
> looking at them all at once, so I'd like to consider them in pairs and
> choose from each pair which one is most important to me. Then I'd like
> to use my answers to those questions to create a ranked list. Anyone
> think they can come up with a good program to quiz me about these items
> pairwise, and output a ranking?
> 
> Extra credit: come up with a solution that lets me take the quiz
> multiple times, and outputs a single ranked list reflecting all of my
> sessions taking the quiz.
> 
> I have my solution to the basic question, but I want to see what other
> people come up with.

Here's a solution that uses tsort, the topological sort module from 
Ruby's standard library. It asks Theta(n^2) questions, but allows me to 
specify that two items on the list are really redundant (and have that 
reflected in the output), and to detect cycles in my preferences that I 
may need to break somehow.

#!/usr/bin/env ruby
require 'rubygems'
require 'enumerator'
require 'facets/core/enumerable/each_unique_pair'
require 'tsort'

class Hash
   include TSort
   alias tsort_each_node each_key
   def tsort_each_child(node, &block)
      fetch(node).each(&block)
   end
end

LIST=["Option 1","Option 2","Option 3","Option 4"]
RESULTS=Hash.new{|h,k| h[k]=[]}
LIST.each{|x| RESULTS[x]}


LIST.enum_for(:each_unique_pair).
   map{|x| x.sort_by{rand}}.
   sort_by{rand}.each do |opt1,opt2|
   printf "1:%s  2:%s ",opt1,opt2
   case readline.chomp
      when "1":
	 RESULTS[opt2] << opt1
      when "2":
	 RESULTS[opt1] << opt2
      when "=":
	 RESULTS[opt1] << opt2
	 RESULTS[opt2] << opt1
      else
	 puts "No preference"
   end
end


puts

#ORDERED LIST
RESULTS.strongly_connected_components.
   each{|list| p list}


-- 
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/