From: Eric Mahurin <eric.mahurin@...>
Date: 2008-06-13T23:36:23+09:00
Subject: Re: [SUMMARY] Preferable Pairs (#165)

------=_Part_5786_29289410.1213367785201
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On 6/12/08, Matthew Moss <matthew.moss@gmail.com> wrote:

>     Solution          Time      Score
>     Andrea Fazzi      0.159     438
>     Dustin Barker     0.020     589
>     Eric Ivancich     4.671     311
>     Steven Hahn       -DNF-
>     Eric Mahurin      0.211     311
>     Matthew Moss      0.022     589
>     Thomas ML         0.114     311


Did anybody try to analyze the complexity of the final solution from Thomas?

The problem with analyzing his solution is this line:

            break unless weight1 * (names.size / 2).floor < maxweight


This causes some dependency on the data for run-time.  It seems like this
line should only be needed for improving runtime, but commenting it out
gives non-optimal results.  Don't get it.  If you ignore this line, the
analysis is easier.  There are O(n**2) pairs and each recursive call
decrements n by 2.  When you get to a single pair, it is O(1).  So,
O(n**2*(n-2)**2*(n-4)**2*...*2**2*1) or O(n!**2).  It is probably more, but
most of this is hidden in the C code (for these size inputs, we can assume
every C method call is O(1)).

My solution is easy to analyze because it doesn't have any data dependent
variation.  It should need to fill a O(2**n) memoization cache which takes
O(n) for each entry - so O(n*2**n).

From the random runs I've done, the ThomML algorithm doesn't look like
O(n!**2) at all.  The randomized complexity looks similar to my O(n*2**n)
algorithm based on random input experiments.

I was wondering if a worst case scenario could make his algorithm behave
more like O(n!**2).  I tried two extreme scenarios: a) love-hate: the more
one player loves another, the more the second player hates the first, b)
popularity: each player has a popularity ranking and every player will
prefer in the popularity order.

I found some interesting results with these extremes.  The love-hate case
allowed the ThomML algorithm to go up to hundreds of players (400 players in
30seconds).  Probably O(n**2) or O(n**3) for this scenario.  The popularity
case was quite bad though - 14 players: 19s,  12 players: 1.8s, 10 players:
0.2s.  This looks to be O(n!).

My algorithm doesn't have these extreme variations.  For all cases, 24
players: 3.8s, 26 players: 10s, 28 players: 30s.

The script I used to generate input for these cases in below.  The first arg
is the # players.  Here's what you can use for the second arg:
nothing/default/-2: the popularity case, -1: love-hate case, 0: random w/o
seeding, >0: random w/ seeding.

Eric

#!/usr/bin/env ruby

NAMES = %w(Adam Anna Bob Betty Chuck David Daria Evan Ellen Fred Faye
Greg Gail Hank Helen Irene John Janet Laura Matt Maria Nadine Oleg
Olivia Peter Pamela Rick Rosa Steve Susan Theo Tracy Vicki Walter)

def sample(n, seed)
 srand(seed) if seed>0
 names = NAMES.clone
 i = 1
 while names.size<n
   i += 1
   NAMES.each { |name| names << "#{name}#{i}" }
 end
 names = names[0, n].sort!
 prefs = Hash.new { |h,k| h[k] = [] }
 names.each { |name1|
   i = 0
   names2 = (seed>=0) ? names.sort_by { rand } : names
   names2.each { |name2|
     next if name2==name1
     next if prefs[name1].include?(name2)
     while prefs[name1][i]
       i += 1
     end
     prefs[name1][i] = name2
     if seed==-1
       !prefs[name2][names.size-2-i] or raise("#{name2} #{i}
#{prefs.inspect}")
       prefs[name2][names.size-2-i] = name1
     end
   }
 }
 names.each { |name|
   puts("#{name}: #{prefs[name].join(' ')}")
 }
end

sample(Integer(ARGV[0] || 10), Integer(ARGV[1]||-2))

------=_Part_5786_29289410.1213367785201--