From: Rick DeNatale <rick.denatale@...>
Date: 2007-10-17T03:22:13+09:00
Subject: Re: Ruby for arranging fencing competitions

On 10/16/07, Milo Thurston <knirirr@gmail.com> wrote:
> Sport fencing competitions are organised in pools, where every fencer
> fences every other and the total score is totted up at the end. Sheets
> like this are used to keep track of which bouts have been played and
> what the score is:
> http://www.soton.ac.uk/~fencing/files/pool.pdf
> These sheets show an order of bouts for between 4-7 fencers, a typical
> number in a pool. An impending competition* got me wondering how one
> might use Ruby to generate those lists of bouts. A simple list of what
> bouts need to be fought is easy, and I wrote a simple script that
> produces an array of the following values for any number of contestants
> (in this case 4):
>
> 1 - 2
> 1 - 3
> 1 - 4
> 2 - 3
> 2 - 4
> 3 - 4
>
> The difficult bit is that fencers need to be given a rest between bouts
> if possible, so this order won't do. Simply randomising this array may
> still mean someone having to do more than one fight in a row. Not having
> a mathematical background I can't think of a suitable method to approach
> this, and if anyone could suggest some hints I'd be interested to know.

How about:

class RoundRobinPairsGenerator

  attr_reader :competitors, :full_size

  def initialize(n)
    @competitors = (1..n).to_a
    @full_size =  (n*n - n) / 2
  end

  def pairings
    @pairings ||= compute_pairings
  end

  private

  def more_tired(played, pair)
    appearances = played.flatten
    pair.sort_by {|comp| appearances.select { |e| e == comp }.length}.last
  end

  def compute_pairings
    pairings = []
    picks = competitors.dup
    while pairings.length < full_size
      trial_pair = picks[0..1].sort
      if pairings.include?(trial_pair)
        more_tired = more_tired(pairings, trial_pair)
        picks.delete(more_tired)
        picks << more_tired
      else
        pairings << trial_pair
        picks << picks.shift
        picks << picks.shift
      end
    end
    pairings
  end
end
puts "For n = 4"
RoundRobinPairsGenerator.new(4).pairings.each { |p| p p }
puts
puts "For n = 10"
RoundRobinPairsGenerator.new(10).pairings.each { |p| p p }


produces:
For n = 4
[1, 2]
[3, 4]
[1, 3]
[2, 4]
[1, 4]
[2, 3]

For n = 10
[1, 2]
[3, 4]
[5, 6]
[7, 8]
[9, 10]
[1, 3]
[4, 5]
[6, 7]
[8, 9]
[2, 10]
[1, 4]
[5, 7]
[8, 10]
[2, 3]
[1, 6]
[5, 9]
[2, 8]
[3, 6]
[7, 9]
[4, 10]
[1, 5]
[2, 7]
[3, 5]
[4, 8]
[6, 9]
[1, 10]
[3, 9]
[2, 4]
[5, 10]
[6, 8]
[1, 9]
[4, 7]
[2, 5]
[3, 8]
[7, 10]
[4, 6]
[2, 9]
[1, 8]
[6, 10]
[3, 7]
[1, 7]
[3, 10]
[2, 6]
[5, 8]
[4, 9]



-- 
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/