Apparently some people around here can’t stand Ruby Q. 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.
–Ken
On 5/3/07, Ken B. [email protected] wrote:
Apparently some people around here can’t stand Ruby Q. 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?
Thanks much for filling in. I’m very interested, and I hope I have
the time to take a shot at this one.
Could you elaborate on the rules a bit? Do all possible pairs have to
be evaluated, or should it deduce values based on previous answers?
banana is more important than apple
orange is more important than banana
no need to compare apples to oranges (pardon the pun).
Ken B… PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
PS: typo on your home page: ‘contected’, looks bad for a linguistics
major 
On 5/3/07, Ken B. [email protected] wrote:
Ken B… PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
I wrote a webapp that did something like that using a perverted
Condorcet method described here: http://xkcd.com/date/algorithms.html.
I don’t have the code anymore, but that’s a concise way fo doing it.
— Bill G. [email protected] wrote:
orange is more important than banana
no need to compare apples to oranges (pardon the
pun).
I think it would be more fun to leave possibilities
like this open:
banana is more important than apple
orange is more important than banana
and apple is more important than orange
In the absence of more data, we can’t rank them, but
add a few more “things”, and you might be able to
(orange is more important than cereal, but apple is
not).
Hmmm, have to think about this.
On Fri, 04 May 2007 09:41:51 +0900, Bill G. wrote:
pairwise, and output a ranking?
Thanks much for filling in. I’m very interested, and I hope I have the
time to take a shot at this one.
Could you elaborate on the rules a bit? Do all possible pairs have to
be evaluated, or should it deduce values based on previous answers?
banana is more important than apple
orange is more important than banana
no need to compare apples to oranges (pardon the pun).
I guess I’d want to know if I ran into a cycle, but I know that’s a lot
more questions. Something else that I would find interesting is having a
way to determine the top 10 asking the minimum number of questions. So
implement whatever answer you prefer.
–Ken
P.S. I think the Ruby Q. needs a fourth rule: don’t ask too many
questions about what the rules of a particular quiz are. Your variation
on the problem may have interesting techniques that nobody else’s has.
On 5/3/07, Ken B. [email protected] wrote:
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?
When does the “no spoiler” period end?
On May 4, 2007, at 9:41 AM, Bill G. wrote:
PS: typo on your home page: ‘contected’, looks bad for a
linguistics major 
–
Bill G. (aka aGorilla)
The best answer to most questions is “it depends”.
On the contrary, linquistics doesn’t require perfect spelling.
Ken B. wrote:
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.
Topological sort. “man tsort” on most *nix systems, or
http://en.wikipedia.org/wiki/Topological_sorting#Algorithms.
The rest is just I/O.
On 5/3/07, Ken B. [email protected] wrote:
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?
The way I see it, ranking is nothing more than sorting and choosing
between pairs is just the comparison of the sort. So, here is a
one-liner given the item list in a file and the questions on stdin:
ruby -e ‘puts(ARGF.read.split.sort { |a,b| print “1: #{a}\n2: #{b}\n”;
STDIN.gets.to_i*2-3}.inspect)’
Eric
On Thu, 03 May 2007 18:49:09 -0500, Ken B. wrote:
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}