Generando un cronograma natural para una liga deportiva

Question

Estoy buscando un algoritmo para generar un cronograma para un conjunto de equipos . Por ejemplo, imagine una temporada deportiva en la que cada equipo juegue entre sí, una vez como equipo de casa y la otra como un equipo visitante en campo de otro equipo.

Para generar un conjunto de todos los partidos en la temporada es fácil, si los equipos es una lista de los equipos de la siguiente haría:

set((x, y) for x in teams for y in teams if x != y) 

Pero también quiero pedir los juegos en orden cronológico en tales una forma que cumple la restricción de un horario de juego válido y también parece "naturalmente aleatorio".

La restricción es que la lista de juegos debe ser agrupables en una serie de rondas en las cada ronda consta de n/2 juegos (donde N es el número de equipos ) en el que cada equipo está emparejado con otro.

Para hacer que el horario parezca más natural, dos equipos no deben enfrentar cada otro dos veces en rondas consecutivas. Es decir, si (a, b) se juega en una ronda , el juego (b, a) no debe jugarse en el campo ext.

Además, tanto como sea posible, todos los equipos deben jugar cada dos asaltos como el equipo visitante y las otras rondas como el equipo local. No creo que es posible cumplir siempre esta restricción, por lo que es más agradable tener . Por ejemplo, un equipo no debería jugar 8 partidos en casa y , luego 8 juegos fuera.

A continuación se muestra lo que obtuve ahora. El principal problema con el algoritmo es que se queda atascado en el while-loop con bastante frecuencia. Especialmente cuando el número de equipos es 16 o más. También es muy ineficiente porque se basa en el uso de la función muestra aleatoria y con la esperanza de hacerlo bien:

from random import sample 
def season_schedule_order(teams, pairs): 
    n_games_per_round = len(teams) // 2 
    last_pairs = set() 
    while pairs: 
     r_pairs = set(sample(pairs, n_games_per_round)) 
     # Check that each team is present once in the round. 
     r_teams = set(x for (x, y) in r_pairs) | set(y for (x, y) in r_pairs) 
     if r_teams != teams: 
      continue 
     # Check that two teams doesn't face each other again. 
     rev_pairs = set((y, x) for (x, y) in r_pairs) 
     if rev_pairs & last_pairs: 
      continue 
     pairs -= r_pairs 
     for p in r_pairs: 
      yield p 
     last_pairs = r_pairs 

teams = set(['aik', 'djurgarden', 'elfsborg', 'gais', 
      'gefle', 'hacken', 'halmstad', 'helsingborg']) 
pairs = set((x, y) for x in teams for y in teams if x != y) 
for (ht, at) in season_schedule_order(teams, pairs): 
    print '%-20s %-20s' % (ht, at) 

Answer 1

he encontrado un método here el que me he adaptado un poco a esto:

def round_robin(units, sets = None): 
    """ Generates a schedule of "fair" pairings from a list of units """ 
    count = len(units) 
    sets = sets or (count - 1) 
    half = count/2 
    for turn in range(sets): 
     left = units[:half] 
     right = units[count - half - 1 + 1:][::-1] 
     pairings = zip(left, right) 
     if turn % 2 == 1: 
      pairings = [(y, x) for (x, y) in pairings] 
     units.insert(1, units.pop()) 
     yield pairings 

teams = ['a', 'b', 'c', 'd'] 
print list(round_robin(teams, sets = len(teams) * 2 - 2)) 

Ahora solo necesito convertir esto en plpgsql. :)

Answer 2

REQUIREMENTS for the BALANCED ROUND ROBIN algorithm 
The requirements of the algorithm can be defined by these four rules: 
1) All versus all 
Each team must meet exactly once, and once only, the other teams in the division league. 
If the division is composed of n teams, the championship takes place in the n-1 rounds. 
2) Alternations HOME/AWAY rule 
The sequence of alternations HOME/AWAY matches for every teams in the division league, should be retained if possible. 
For any team in the division league at most once in the sequence of consecutive matches HAHA, occurs the BREAK of the rhythm, i.e. HH or AA match in the two consecutive rounds. 
3) The rule of the last slot number 
The team with the highest slot number must always be positioned in the last row of the grid. 
For each subsequent iteration the highest slot number of grid alternates left and right position; left column (home) and right (away). 
The system used to compose the league schedule is "counter-clockwise circuit." 
In the construction of matches in one round of the championship, a division with an even number of teams. 
If in a division is present odd number of teams, it will be inserted a BYE/Dummy team in the highest slot number of grid/ring. 
4) HH and AA are non-terminal and not initial 
Cadence HH or AA must never happen at the beginning or at the end of the of matches for any team in the division. 
Corrective inversion RULE performs only once, in the bottom line in the RING, LeftRight redundant inversion flip-flop RULE, so we will never obtain in the last two rounds CC or FF. 
Round Robin ALGORITHM 
The algorithm that satisfies rule (1) is obtained with a simple algorithm Round Robin: 
where every successive round is obtained applying to the slot numbers ring a "counterclockwise" rotation. 
To satisfy the rule (2) we must "improve", the simple round robin algorithm by performing balancing of Home and Away sequence. 
It is performed by applying several "counterclockwise" rotations in the slot numbers ring in order to obtain acceptable combinations of slot positions for the next round. 

The number of rotations required in the ring is (n/2 -1). 
So we will get that in the two successive rounds, almost all the teams playing at home in the previous round, will play away from home in the next round. 
DATA STRUCTURE 
n_teams: (4,6,8,..,20) 
n_rounds: n_teams -1; 

Ring - Circuit anillo es tal estructura de datos, es decir, un tipo particular de secuencia en la que son realizables y formalmente algorítmicamente definido: operación de (en sentido antihorario) de rotación entre elementos de anillo y la INSERT_LAST_TEAM operación, El contenido del anillo define todas las coincidencias para cada ronda en particular en el calendario de coincidencias Ring.Length es un número par igual a n_teams Subsecuencia Left_ring: Subsecuencia Ring con elementos de 1 a n/2. SubSecuencia Right_ring: Suena la subsecuencia con elementos de n/2 + 1 a n. Coincidencia [i] = Ring_element [i]: Ring_element [n - i + 1]; donde i = 1 a n/2 El PARTIDO es un par ordenado compuesto por dos EQUIPOS, (Equipo_de_casa: Equipo_de_viaje). primera ronda Inicio: Lejos 01:07 02:06 03:05 04:08

Next_Iteration is obtained by applying these rules: 
a) perform (n/2 – 1) times * ANTI CLOCKWISE ROTATIONs 
b) all right column elements, below the last team, will be shifted upwards 
c) INSERT_LAST_TEAM 
(Insert_Last_Element_into_ Ring_onLeft (n) or 
Insert_Last_Element_into_Ring_onRight(n), alternatively) 
d.1) Last Line LeftRight redundant swap RULE 
eventually have to swap elements in the last row once again 
d.1) last team left/right - flip/flop 



In the following example it will be explained how the Ring elements of 8 teams 
are gradually transformed in five steps, 
from from the SECOND ROUND into the THIRD ROUND. 
If we start from from the SECOND ROUND: 
05 :04 
06 :03 
07 :02 
08 :01 
a. After we perform THREE Anti-clockwise rotations, (n =8, 3 = 8/2 -1) 
we will get the situation like this: 
02 :01 
03 :08 
04 :07 
05 :06 
b. When we apply the LAST SLOT RULE: 
the right column elements (06,07) below last team (08) will be shifted upwards 
02 :01 
03 
04 :07 
05 :06 
c. And now we will apply the LAST SLOT RULE-bottom right, 
we will get the situation which describes the THIRD ROUND: 
(08 must be moved to the bottom right position) 
02 :01 
03 :07 
04 :06 
05 :08 
d.1 Now it will be checked if for this iteration number (i.e. round) 
depending on CODE SIX or ZERO Cadence, we eventually have to 
swap elements in the last row redundantly, 
Left/Right swaping 
d.2 And at the end we will apply the LAST TEAM SLOT ROULE 
swap left & right elements, 
if in the previous iteration last team was positioned on the right, 
in this iteration it should be positioned on the left bottom position, 
so the last line elements will be swapped, else do nothing. 
THIRD ROUND: 
02 :01 
03 :07 
04 :06 
05 :08 

read more

Here is the snippet of the code in Perl.