Ruby combinatorics

Question

I want to generate a soccer football fixture with a list of clubs. Each game is played on Sundays in a random time included in the match_starts_at array. Each club plays only one game each Sunday.

Example:

Having these clubs:

Club Atlético All Boys
Asociación Atlética Argentinos Juniors
Arsenal Fútbol Club
Club Atlético Banfield
Club Atlético Belgrano
Club Atlético Boca Juniors
Club Atlético Colón
Club Estudiantes de La Plata
Club Deportivo Godoy Cruz Antonio Tomba
Asociación Mutual Social y Deportiva Atlético de Rafaela
Club Atlético Independiente
Club Atlético Lanús
Club Atlético Newell's Old Boys
Club Olimpo
Racing Club
Club Atlético San Martín
Club Atlético San Lorenzo de Almagro
Club Atlético Tigre
Club Atlético Unión
Club Atlético Vélez Sarsfield

Result should be similar to what is seen here: http://www.afa.org.ar/index.php?option=com_content&view=article&id=16780%3Afixture-del-torneo-de-primera-division&Itemid=100

Club structure example:

=> # Club @id=1 @name="Example Name"

=> # Club @id=2 @name="Example2 Name"

Fixture structure example:

=> # Fixture @id=1 @datetime='2011-11-19 19:12:49' @home_id=1 @away_id=2

A Fixture object needs the following to be saved to the database:

a home club (:home)    
an away club (:away)    
and the time of the match (:datetime)

Each club should play only one time with the other clubs and all clubs should play one match at home, the other away , the other at home, etc. There should be 10 matches in a date. How can I create the list of matches?

This is what I've done so far.

  competition = Competition.get(1)
  clubs = Club.all #20 clubs
  @time = Time.now
  @count = 0
  until @time.sunday? do
     @time += (24*60*60) # add 1 day until it's sunday
  end
  @first_time = @time
  @fixture = {1 => []}
  clubs.combination(2).each_with_index do |(club1, club2), idx|
    Fixture.create(
      :home => idx.even? ? club1 : club2,
      :away => idx.even? ? club2 : club1,
      :datetime =>  available_fixture_date(club1,club2)
    ).save
  end

  def getFecha(club1, club2)
    @fixture.keys.each do |fecha|
      if (!@fixture[fecha].include?(club1.name) && !@fixture[fecha].include?(club2.name))
        @fixture[fecha] << club1.name
        @fixture[fecha] << club2.name
        @fixture[@fixture.keys.last + 1] = []
        return fecha
      end
    end
  end

  def available_fixture_date(club1, club2)
    fecha = getFecha(club1, club2)
    match_starts_at = ['16:00', '17:30', '18:10', '22:00']
    match_time = match_starts_at.shuffle.first
    @time  = @first_time + (24*60*60) * fecha * 7
    Time.new(@time.year, @time.month, @time.day, match_time[0,2], match_time[3,2])
 end

With my code I get more than 19 dates and I should get 19 dates with 10 matches per date.

Answer 1

You won't get a nice one-liner for that, like you did for the pairing of teams, since it requires consulting the existing data to find out what dates are already taken. But this should work fine. Note that I've used ActiveSupport's time helpers, but you could use something like Chronic if you don't have ActiveSupport available and don't want to include it.

def available_fixture_date(club1, club2)
  last_played = (club1.fixtures | club2.fixtures).max(:datetime)
  last_played.nil? ? DateTime.now.sunday : last_played + 1.week
end

def create_fixtures(clubs)
  clubs.combination(2).each_with_index do |(club1, club2), idx|
    Fixture.create(
      :home     => idx.even? ? club1 : club2,
      :away     => idx.even? ? club2 : club1,
      :datetime =>  available_fixture_date(club1, club2)
    )
  end
end

Answer 2

I believe the general algorithm you're looking for here is the Round-Robin. The following gets the dates correctly for me, ending up with 19 dates total, 10 matches per date:

DAY = 24 * 60 * 60
MATCH_START_TIMES = ['16:00', '17:30', '18:10', '22:00']

def fixture_date(fecha)
  # select a random start time
  match_time = MATCH_START_TIMES.sample

  @time = @first_time + DAY * fecha * 7
  Time.new(@time.year, @time.month, @time.day, match_time[0,2].to_i, match_time[3,2].to_i)
end

# uses round-robin indexing algorithm described on
# http://en.wikipedia.org/wiki/Round-robin%5Ftournament#Scheduling_algorithm
def round_robin(n, round)
  arr = [*0...n]
  arr.insert 1, *arr.pop(round)
  [arr.slice(0, n/2), arr.slice(n/2, n).reverse]
end

def find_club_combination(clubs, round, pair)
  indexes = round_robin(clubs.size, round)
  index_a, index_b = indexes.first[pair], indexes.last[pair]
  [clubs[index_a], clubs[index_b]]
end

competition = Competition.get(1)
clubs = Club.all #20 clubs
@time = Time.now
@count = 0
@time += DAY until @time.sunday?

@first_time = @time

num_rounds = clubs.size - 1
matches_per_day = clubs.size / 2
(0...num_rounds).collect do |round|
  matches_per_day.times do |pair|
    club1, club2 = find_club_combination(clubs, round, pair)
    Fixture.create(
      :home => round.even? ? club1 : club2,
      :away => round.even? ? club2 : club1,
      :datetime => fixture_date(round)
    ).save
  end
end