From: Max Muermann <ruby@...>
Date: 2006-12-11T12:12:44+09:00
Subject: Re: [QUIZ] Tournament Matchups (#105)

Here's my solution. It assumes that the teams are ranked by skill. I
wanted to see whether this could be done in-place and am doing some
recursive swapping to arrive at the correct solution.

There's an additional pass through the array at the end to remove
cases where two teams have received byes for the first round and are
scheduled to play each other in the second round.
No pretty printing - sorry. Byes are nil in the resulting array of pairings.

Here are some results:

"8 players:"
[[1, 8], [4, 5], [2, 7], [3, 6]]

"6 players:"
[[1, nil], [4, 5], [2, nil], [3, 6]]

"16 players:"
[[1, 16], [8, 9], [4, 13], [5, 12], [2, 15], [7, 10], [3, 14], [6, 11]]

"11 players:"
[[1, nil], [8, 9], [4, 5], [2, nil], [7, 10], [3, nil], [6, 11]]

"32 players:"
[[1, 32], [16, 17], [8, 25], [9, 24], [4, 29], [13, 20], [5, 28], [12,
21], [2, 31], [15, 18], [7, 26], [10, 23], [3, 30], [14, 19], [6, 27],
[11, 22]]

Cheers,
Max


require 'enumerator'

# swap the second quarter of an array with the last quarter
def swap_interleaved(a)
  n = a.size >> 2
  a[n..2*n-1],a[3*n..4*n-1] = a[3*n..4*n-1],a[n..2*n-1]
end

# swap the third quarter of an array with the last quarter
def swap(a)
  n = a.size >> 2
  a[2*n..3*n-1],a[3*n..4*n-1] = a[3*n..4*n-1],a[2*n..3*n-1]
end

# for the given array, swap_interleaved, then swap
# if level is not reached, split array in half and recurse for both halves
def rec(a, level)
  swap_interleaved a
  swap(a)
  if (level>0)
    a[0..a.size/2-1] = rec(a[0..a.size/2-1], level-1)
    a[a.size/2..-1] = rec(a[a.size/2..-1], level-1)
  end
  a
end

def match_up(num_players)
  # match up first-round pairings
  n = (Math.log(num_players-1)/Math.log(2)).to_i+1

  # new array (2**n in size)
  a = Array.new(2**n)

  # add players
  a[0..num_players-1] = (1..num_players).to_a

  # make first-round pairings
  a = a[0..a.size/2-1].zip(a[a.size/2..-1].reverse)

  # recurse
  (n-3).downto(0) do |l|
    rec(a,l)
  end

  # remove double byes
  result = []
  a.each_slice(2) do |a,b|
    if a[1] || b[1]
      result << a << b
    else
      result << [a[0],b[0]]
    end
  end
  result
end

p "8 players:"
p match_up(8)

p "6 players:"
p match_up(6)

p "16 players:"
p match_up(16)

p "11 players:"
p match_up(11)

p "32 players:"
p match_up(32)