¿Cómo puedo generar un calendario de torneos en Ruby?

Question

He estado buscando en todas partes, incluidos los archivos de Stack Overflow, para obtener una respuesta sobre cómo hacerlo, he intentado rodar la mía, pero han quedado cortos, así que decidí publicar mi solicitud aquí.

Necesito tomar un número arbitrario (par) de elementos en una matriz y regresar con el elemento emparejado con otro elemento en la matriz. Necesito que la salida del código sea la misma que el ejemplo de salida que he incluido a continuación.

de entrada:

 
('A'..'H').to_a 

Salida:

 
[[['A','H'], ['B','G'], ['C','F'], ['D','E']], 
[['A','G'], ['B','F'], ['C','E'], ['D','H']], 
[['A','F'], ['B','E'], ['C','D'], ['G','H']], 
[['A','E'], ['B','D'], ['C','H'], ['F','G']], 
[['A','D'], ['B','C'], ['E','G'], ['F','H']], 
[['A','C'], ['B','H'], ['D','G'], ['E','F']], 
[['A','B'], ['C','G'], ['D','F'], ['E','H']]] 

¿Alguna idea?

Esto es lo que he hecho hasta ahora. Está un poco sucio y no regresa en el orden que necesito.

 
items = ('A'..'H').to_a 
combinations = [] 

1.upto(7) do |index| 
    curitems = items.dup 
    combination = [] 
    1.upto(items.size/2) do |i| 
    team1 = curitems.delete_at(0) 
    team2 = curitems.delete_at(curitems.size - index) || curitems.delete_at(curitems.size - 1) 
    combination << [team1, team2] 
    end 
    combinations << combination 
end 

pp combinations 

La salida está cerca, pero no en el orden correcto:

 
[[["A", "H"], ["B", "G"], ["C", "F"], ["D", "E"]], 
[["A", "G"], ["B", "F"], ["C", "E"], ["D", "H"]], 
[["A", "F"], ["B", "E"], ["C", "D"], ["G", "H"]], 
[["A", "E"], ["B", "D"], ["C", "H"], ["F", "G"]], 
[["A", "D"], ["B", "C"], ["E", "G"], ["F", "H"]], 
[["A", "C"], ["B", "H"], ["D", "E"], ["F", "G"]], 
[["A", "B"], ["C", "G"], ["D", "H"], ["E", "F"]]] 

Se dará cuenta de que mi código me consigue dos < D - combinaciones> H (última línea y de segunda línea) y eso no funcionará

Mi comprensión de los requisitos de la OP [FM]:

• Dado N equipos (por ejemplo, 8 equipos: A..H).
• Crear un calendario de torneos, que consiste en R rondas de juego (7 en nuestro ejemplo) y G juegos (28 en nuestro ejemplo).
• Donde cada equipo juega a cada otro equipo exactamente una vez.
• Donde cada equipo juega una vez en cada ronda.
• Y (la parte dura) donde el orden de los juegos dentro de una ronda funciona así:
• El equipo mejor clasificado (A) se reproduce el equipo de bajo clasificado (H) en primer lugar.
• Si un duelo candidato es rechazado por violar la norma de no repetición, poner el equipo de bajo clasificado en la "un segundo plano" y forman los otros duelos primero. Luego haga coincidir los equipos de back-burner con las mismas reglas . (Por ejemplo: en la Ronda 2, el primer partido candidato, A-H, se rechazaron como una repetición, por lo que el juego 1 se ser A-G y H se sentará en un segundo plano , para ser emparejado con D como el última juego en la ronda).
• Al agregar equipos al back-quemador, agréguelos al principio de esa lista (es decir, conserve el orden de rango en el quemador de fondo también).
• Nota: Round 5 es el complicado. Los primeros 2 juegos de son sencillos. El tercer juego sería E-H; sin embargo, eso crea un escenario donde el 4to juego sería una repetición (F-G). Por lo tanto, el algoritmo necesita retroceder, rechazar E-H vincular y en su lugar ir por E-G en el 3er juego.

Answer 1

Bueno, puedo obtener su ejemplo de 8 equipos correctamente, pero no sé cómo generalizar el ajuste. Pero tal vez esto va a hacerle pensar ...

games = (1...teams.size).map do |r| 
    t = teams.dup 
    (0...(teams.size/2)).map do |_| 
    [t.shift,t.delete_at(-(r % t.size + (r >= t.size * 2 ? 1 : 0)))] 
    end 
end 

Answer 2

Parece que desea un horario de turnos. El principio es sencillo:

Si se inicia con esta configuración (equipos de la fila superior que juegan contra el equipo inferior correspondiente):

A B C D 
H G F E 

configurar un equipo como fijos (por ejemplo, A) y girar el resto (por ejemplo, las agujas del reloj):

A H B C  A G H B  A F G H  A E F G A D E F A C D E 
G F E D  F E D C  E D C B  D C B H C B H G B H G F 

Voilà, 7 rondas, y cada equipo juega cada uno otro equipo.

Editar: Cambié el orden de enumeración en este ejemplo para reflejar su salida de ejemplo, pero esto solo obtiene los oponentes de A a la derecha.

Answer 3

¿Qué tal

[*'A'..'H'].permutation(2).to_a 
=> [["A", "B"], ["A", "C"], ["A", "D"], ["A", "E"], ["A", "F"], ["A", "G"], ["A", "H"], ["B", "A"], ["B", "C"], ["B", "D"], ["B", "E"], ["B", "F"], ["B", "G"],.... 

Editar: Sólo se dio cuenta de la salida no está en el formato deseado, pero tal vez es todavía útil para alguien más.

Answer 4

Pido disculpas por el Python-ness de este código. Con un poco de suerte, alguien traducirá.

def tourney(teams): 
    N = len(teams) 
    R = N-1 # rounds 
    M = N/2 # matches per round 
    sched = [[None] * M for i in range(R)] 
    played = set() 

    def fill(i, t): 
     # Replenish t at the start of each round. 
     if i % M == 0: 
      t = teams[:] 

     # Pick out the highest-seeded team left in t. 
     topseed = t.pop(min(range(len(t)), key=lambda i: teams.index(t[i]))) 

     # Try opponents in reverse order until we find a schedule that works. 
     for j, opp in reversed(list(enumerate(t))): 
      match = topseed, opp 
      if match not in played: 
       # OK, this is match we haven't played yet. Schedule it. 
       sched[i // M][i % M] = match 
       played.add(match) 

       # Recurse, if there are any more matches to schedule. 
       if i + 1 == R * M or fill(i + 1, t[j+1:]+t[:j]): 
        return True # Success! 

       # If we get here, we're backtracking. Unschedule this match. 
       played.remove(match) 
     return False 

    if not fill(0, []): 
     raise ValueError("no schedule exists") 
    return sched 

Answer 5

Aquí es una aplicación en Ruby 1.8.6 según la especificación del FM que la salida correcta para 8 equipos (Muchas gracias a FM por el gran trabajo!):

#!/usr/bin/env ruby 

require 'pp' 
require 'enumerator' 

class Array 
    # special round robin scheduling 
    def schedule 
    res, scheduled = [], [] 
    (length-1).times { dup.distribute(scheduled, []) } 
    # convert list of games to list of rounds 
    scheduled.each_slice(length/2) {|x| res.push x} 
    aux = res.inject {|a, b| a+b} 
    raise if aux.uniq.length != aux.length 
    res 
    end 
    # pair the teams in self and backburner and add games to scheduled 
    def distribute(scheduled, backburner) 
    # we are done if list is empty and back burners can be scheduled 
    return true if empty? && backburner.empty? 
    return backburner.distribute(scheduled, []) if empty? 
    # take best team and remember if back burner list offered alternatives 
    best, alternatives = shift, !backburner.empty? 
    # try each team starting from the last 
    while other = pop do 
     # add team to the back burner list if best played it already 
     if scheduled.include? [best, other] 
     backburner.unshift(other) 
     next 
     end 
     # schedule the game 
     scheduled.push [best, other] 
     # try if rest can be scheduled 
     return true if dup.distribute(scheduled, backburner.dup) 
     # if not unschedule game and add other to back burner list 
     scheduled.pop 
     backburner.unshift(other) 
    end 
    # no possible opponent was found, so try alternatives from back burners list 
    return alternatives && backburner.unshift(best).distribute(scheduled, []) 
    end 
end 

pp %w{ A B C D E F G H }.schedule 

__END__ 

Output: 
[[["A", "H"], ["B", "G"], ["C", "F"], ["D", "E"]], 
[["A", "G"], ["B", "F"], ["C", "E"], ["D", "H"]], 
[["A", "F"], ["B", "E"], ["C", "D"], ["G", "H"]], 
[["A", "E"], ["B", "D"], ["C", "H"], ["F", "G"]], 
[["A", "D"], ["B", "C"], ["E", "G"], ["F", "H"]], 
[["A", "C"], ["B", "H"], ["D", "G"], ["E", "F"]], 
[["A", "B"], ["C", "G"], ["D", "F"], ["E", "H"]]] 

Answer 6

fin tuve tiempo para ver esto de nuevo Esta es una versión Ruby de la respuesta de Jason, con algunas simplificaciones y un par de buenas ideas de la respuesta de la jarra.

require 'pp' 

def tournament (teams) 
    teams.reverse! 

    # Hash of hashes to keep track of matchups already used. 
    played = Hash[ * teams.map { |t| [t, {}] }.flatten ] 

    # Initially generate the tournament as a list of games. 
    games = [] 
    return [] unless set_game(0, games, played, teams, nil) 

    # Convert the list into tournament rounds. 
    rounds = [] 
    rounds.push games.slice!(0, teams.size/2) while games.size > 0 
    rounds 
end 

def set_game (i, games, played, teams, rem) 
    # Convenience vars: N of teams and total N of games. 
    nt = teams.size 
    ng = (nt - 1) * nt/2 

    # If we are working on the first game of a round, 
    # reset rem (the teams remaining to be scheduled in 
    # the round) to the full list of teams. 
    rem = Array.new(teams) if i % (nt/2) == 0 

    # Remove the top-seeded team from rem. 
    top = rem.sort_by { |tt| teams.index(tt) }.pop 
    rem.delete(top) 

    # Find the opponent for the top-seeded team. 
    rem.each_with_index do |opp, j| 
     # If top and opp haven't already been paired, schedule the matchup. 
     next if played[top][opp] 
     games[i] = [ top, opp ] 
     played[top][opp] = true 

     # Create a new list of remaining teams, removing opp 
     # and putting rejected opponents at the end of the list. 
     rem_new = [ rem[j + 1 .. rem.size - 1], rem[0, j] ].compact.flatten 

     # Method has succeeded if we have scheduled the last game 
     # or if all subsequent calls succeed. 
     return true if i + 1 == ng 
     return true if set_game(i + 1, games, played, teams, rem_new) 

     # The matchup leads down a bad path. Unschedule the game 
     # and proceed to the next opponent. 
     played[top][opp] = false 
    end 

    return false 
end 

pp tournament(ARGV) 

Answer 7

Escribí recientemente una gema que ayuda en el proceso de generación de horarios de turnos. Puede give it a try.

Answer 8

La respuesta seleccionada aquí me dio problemas. Parece relacionado con el enfoque delete_at donde se mueve hacia atrás en la matriz de equipos. Inevitbaly dos equipos juegan entre sí más de una vez antes de lo que deberían. Solo lo noté cuando fui a 16 equipos, pero creo que también ocurre en 8 equipos ...

así que codifiqué el algo de Svante, que es inteligente y funciona con cualquier cantidad de equipos.También estoy girando en sentido antihorario, no agujas del reloj

equipos suponiendo es un objeto de modelo de aquí, y num_teams es el número de equipos

@tms = teams.all  
    matchups_play_each_team_once = (0...num_teams-1).map do |r| 
    t = @tms.dup 
    first_team = t.shift 
    r.times do |i| 
     t << t.shift 
    end 
    t = t.unshift(first_team) 
    tms_away = t[0...num_teams/2] 
    tms_home = t[num_teams/2...num_teams].reverse 
    (0...(num_teams/2)).map do |i| 
     [tms_away[i],tms_home[i]] 
    end 
    end 

Answer 9

Basándose en esta información en this link el siguiente código de Ruby es lo que utilizo para generar la programación de round-robin:

def round_robin(teams) 
    raise "Only works for even number of teams" unless teams.length.even? 
    first = teams.shift        # Put one team in the middle, not part of the n-gon 
    size = teams.length        # The size of the n-gon without one team 
    pairs = (1..(size/2)).map{ |i| [i,size-i].sort } # The 'lines' that connect vertices in the n-gon 
    (0...size).map{         
    teams.unshift(teams.pop)      # Rotate the n-gon 
    # Combine the special case with the vertices joined by the lines 
    [ [ first, teams[0] ], *pairs.map{ |a,b| [ teams[a], teams[b] ] } ] 
    } 
end 

teams = ('A'..'H').to_a 
schedule = round_robin(teams) 
puts schedule.map{ |round| round.map{ |teams| teams.join }.join(' ') } 
#=> AH BG CF DE 
#=> AG HF BE CD 
#=> AF GE HD BC 
#=> AE FD GC HB 
#=> AD EC FB GH 
#=> AC DB EH FG 
#=> AB CH DG EF 

Answer 10

creé una joya, round_robin_tournament la que le puede resultar útil.

Sólo tiene que ejecutar

students = %w(John Paul Ringo George) 
teams = RoundRobinTournament.schedule(students) 

Y teams habrá una gran variedad de cada día, cada día que es un conjunto de parejas.