Come posso generare un programma di torneo in Ruby?

Question

Ho cercato dappertutto, inclusi gli archivi Stack Overflow, per una risposta su come farlo, ho provato a far girare il mio, ma sono venuto a mancare, così ho deciso di pubblicare la mia richiesta qui.

Ho bisogno di prendere un numero arbitrario (pari) di elementi in un array e restituire con l'elemento abbinato a un altro elemento nell'array. Ho bisogno che l'output del codice sia uguale all'esempio di output che ho incluso di seguito.

ingresso:

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

uscita:

 
[[['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']]] 

Tutte le idee?

Ecco cosa ho fatto finora. È un po 'sporco, e non sta tornando nell'ordine che mi serve.

 
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 

L'uscita è vicino, ma non nel giusto ordine:

 
[[["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"]]] 

si noterà che il mio codice mi riceve due D < - combinazioni> H (ultima linea e seconda riga) e quello non funzionerà.

mia comprensione delle esigenze del PO [FM]:

• Dato N squadre (ad esempio, 8 squadre: A..H).
• Creare un programma di tornei, composto da R turni di gioco (7 nel nostro esempio) e G giochi (28 a nostro esempio).
• Dove ogni squadra gioca ogni altra squadra esattamente una volta.
• Dove ogni squadra gioca una volta per round.
• E (la parte più difficile), dove l' ordinamento dei giochi all'interno di un round funziona così:
• Il team di top-ranked (A) interpreta il basso squadra classificata (H) prima.
• Se un matchup candidato viene rifiutato per aver violato la regola no-repeat, messo il team di basso rango sul "back-bruciatore" e formano gli altri matchups prima. Quindi abbinare i team di back-burner utilizzando le stesse regole . (Ad esempio: nel Round 2, il primo matchup candidato, A-H, è respinto come una ripetizione, in modo da gara 1 sarà essere A-G, e H siederà nel dimenticatoio , per essere accoppiato con D come ultima gioco a tutto tondo).
• Quando si aggiunge squadre al back-bruciatore, aggiungerli alla parte anteriore di quella lista (vale a dire, conservare rango ordinamento sul back-bruciatore pure).
• Nota: il round 5 è il difficile. I primi 2 giochi sono semplici. Il 3 ° gioco sarebbe allora E-H; tuttavia, ciò crea uno scenario in cui il quarto gioco sarebbe una ripetizione (F-G). Quindi l'algoritmo deve eseguire il backtrack , rifiutare l'abbinamento E-H e passare al numero E-G nel terzo gioco .

Answer 1

Bene, posso ottenere il tuo esempio di 8 squadre giusto, ma non so come generalizzare il tweak. Ma forse questo ti porterà a pensare ...

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

Sembra che tu voglia un programma round robin. Il principio è semplice:

Se si inizia con questa configurazione (squadre in fila superiore che giocano contro il corrispondente squadra inferiore):

A B C D 
H G F E 

si imposta una squadra come fisso (ad esempio, A) e ruotare il riposo (es. in senso orario):

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 turni, e ogni squadra si gioca a vicenda.

Edit: ho cambiato l'ordine di censimento nel questo esempio per riflettere la vostra uscita esempio, ma questo ottiene solo gli oppositori del A destra.

Answer 3

Come su

[*'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"],.... 

Edit: appena notato l'uscita non è nel formato desiderato, ma forse è ancora utile per qualcun altro.

Answer 4

Mi scuso per il Python-ness di questo codice. Con un po 'di fortuna, qualcuno tradurrà.

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

Ecco un'implementazione in Ruby 1.8.6 base alle specifiche del FM dando l'uscita corretta per 8 squadre (Molte grazie a FM per il grande lavoro!):

#!/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

finalmente ho avuto il tempo per rivedere questo. Questa è una versione di Ruby della risposta di Jason, con alcune semplificazioni e un paio di buone idee dalla risposta di Jug.

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

Ho scritto una gemma di recente che aiuta nel processo di generazione di programmi round robin. È possibile give it a try.

Answer 8

La risposta selezionata qui mi ha dato problemi. Sembra correlato all'approccio delete_at in cui ti stai spostando all'indietro sulla serie di squadre. Inevitbaly due squadre si giocano più di una volta prima di quanto dovrebbero. L'ho notato solo quando sono andato a 16 squadre, ma penso che succeda anche a 8 squadre ...

così ho codificato l'algo di Svante che è intelligente e funziona con qualsiasi numero di squadre.Anche io sto ruotando in senso antiorario, non in senso orario

assumendo squadre è un oggetto del modello qui, e num_teams è il numero di squadre

@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

Sulla base di queste informazioni nel this link il seguente codice Ruby è quello che uso per generare scheduling 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

ho creato un gioiello, round_robin_tournament che si potrebbe trovare utile.

Basta eseguire

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

E teams sarà una matrice di ogni giorno, ogni giorno di essere una serie di coppie.