From: Yossef Mendelssohn <ymendel@...>
Date: 2007-10-17T05:50:23+09:00
Subject: Re: Ruby for arranging fencing competitions

On Oct 16, 1:22 pm, "Rick DeNatale" <rick.denat...@gmail.com> wrote:
> On 10/16/07, Milo Thurston <knir...@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 Rubyhttp://talklikeaduck.denhaven2.com/

Nice.

Just in case you (or anyone else) was interested, I quickly threw
together something that would create the simple pairings (1.upto(x) { |
i| (x+1).upto(x) { |j| ... } }) and then attempt to re-order it
afterwards. I didn't have high hopes for it, and it didn't seem to
work for any number (well, any number > 2).

I haven't bothered to work out a mathematical proof or anything, but I
believe it's impossible to generate the pairings that way and then re-
order them. It really should be done this way, taking the rest period
into account when creating the pairings.

--
-yossef