sorting tournament seeds

Question

Estoy haciendo una aplicación web de soporte de eliminación simple/doble con HTML/JS. Estoy luchando para descubrir cómo asignar los partidos de la primera ronda de una lista de equipos/jugadores sembrados. Por ejemplo, en un soporte de 8 jugadores los partidos de primera ronda son:

1V8 4V5 2V7 3v6

En términos más generales, las semillas pueden ser considerados como una matriz (como se le asigno equipos a coincide con hacer que salgan de una matriz): 1,2,3,4,5,6,7,8

que debe ordenarse a: 1,8,4,5,2,7,3 , 6

Para aclarar, las semillas más altas necesitan tener la distancia máxima entre ellas en el s orted array, esto es para que en un soporte sin alteraciones, las semillas más bajas se anulen primero y las coincidencias con las semillas altas ocurran lo más tarde posible. En términos prácticos, piense en un torneo de tenis, donde quiere evitar que los 4 mejores jugadores en un grupo de 16 o 32, etc. jueguen entre sí hasta las semifinales. Por lo tanto, la salida de matriz correcta para un soporte de semilla es:

1,16,8,9,4,13,5,12,2,15,7,10,3,14,6,11

que se traduce en los siguientes 1ª ronda de partidos:

1v16 8v9 4v13 5v12 2v15 7v10 3v14 6v11

Gracias a Matt Ball para el algoritmo correcto para un soporte 8 de semillas

Answer 1

He encontrado una solución, pero está fuera del alcance de simplemente "ordenar matrices".

El código (javascript) está en http://jsbin.com/ukomo5/2/edit.

En términos básicos, el algoritmo supone que no ocurrirán alteraciones en el paréntesis, por lo tanto, las semillas 1 y 2 deben coincidir en la ronda final con. Se itera a través de cada semilla en cada ronda (comenzando desde la gran final precalculada, trabajando hacia atrás), calculando la semilla desconocida en la partida en la ronda anterior que ganó la semilla actual (en la iteración). Esto se puede hacer porque dada una semilla y número redondo, se puede trabajar con lo que debería ser la otra semilla:

otra semilla = número de semillas en todo el + 1 - la semilla conocida

Para ilustrar, en las semifinales:

semifinales 1 (donde la semilla conocido es 1): otra semilla = 4 + 1 - 1 = 4

semifinales 2 (donde la semilla conocido es 2): otra semilla = 4 + 1 - 2 = 3

Me acabo de dar cuenta de este patrón al mirar un soporte "sin molestos" que había dibujado.

En la iteración final (es decir, la ronda 1) se conocen todas las semillas y su posición, listas para ser asignadas a las coincidencias. La matriz ordenada correcta es a continuación:

1,16,8,9,4,13,5,12,2,15,7,10,3,14,6,11

Gracias de nuevo a Matt Ball, quien propuso una solución correcta para corchetes pequeños (es difícil establecer el problema y la solución deseada sin contexto detallado, lo que no hice completamente en mi pregunta inicial).

¡Si alguien tiene otra solución o una versión más elegante de mi solución, háganoslo saber!

Answer 2

Esto no es, probablemente, tan eficiente como @ respuesta de alex utilizando una función personalizada sort, pero sin duda más fácil de escribir y comprender:

// This algorithm assumes that seeds.length is an even number 
var seeds = [1, 2, 3, 4, 5, 6, 7, 8], 
    firstRound = []; 

while (seeds.length) 
{ 
    firstRound.push(seeds.shift()); 
    firstRound.push(seeds.pop()); 
} 

// seeds is now empty 
// firstRound is now [1, 8, 2, 7, 3, 6, 4, 5] 

Demo 1

---

En realidad, me acaba de ocurrir un algoritmo más rápido (en el lugar "clasificación", toma O(n) tiempo):

// Also assumes that seeds.length is an even number 
var seeds = [1, 2, 3, 4, 5, 6, 7, 8], 
    numSeeds = seeds.length, 
    stop = numSeeds >> 1, 
    temp; 

for (var i=1; i<stop; i=i+2) 
{ 
    temp = seeds[i]; 
    seeds[i] = seeds[numSeeds-i]; 
    seeds[numSeeds-i] = temp; 
} 

// seeds is now [1, 8, 3, 6, 5, 4, 7, 2] 

Demo 2

Tenga en cuenta que ninguno de estos algoritmos genera exactamente la misma fin de pares como en el OP, pero ambos generan el mismo establece de pares:

• (1,8)
• (2,7)
• (3,6)
• (4,5)

Answer 3

Las ideas de hacer coincidir jugadores de la parte superior e inferior son correctas pero no del todo completas. Hacerlo una vez que funciona muy bien para la primera ronda:

while (seeds.length) 
{ 
    firstRound.push(seeds.shift()); 
    firstRound.push(seeds.pop()); 
} 
1, 2, 3, 4, 5, 6, 7, 8 => 1, 8, 2, 7, 3, 6, 4, 5 

... pero en la segunda ronda, la semilla de la semilla 1 cumple 2 y 3 cumple 4. Tenemos que hacer la primera pasada aleatoria/para cada ronda. La primera vez, movemos cada elemento individualmente. Segunda vez, movemos cada PAR de elementos. La tercera vez que movemos grupos de cuatro, etc., hasta que nuestro tamaño de grupo sea seeds.length/2. De este modo:

// this is ruby, aka javascript psuedo-code :) 

bracket_list = seeds.clone 

slice = 1 
while slice < bracket_list.length/2 
    temp = bracket_list 
    bracket_list = [] 

    while temp.length > 0 
    bracket_list.concat temp.slice!(0, slice)  # n from the beginning 
    bracket_list.concat temp.slice!(-slice, slice) # n from the end 
    end 

    slice *= 2 
end 
return bracket_list 

Esto es lo que la matriz se parecerá a medida que avanza a través de las iteraciones (entre paréntesis indican el tamaño creciente grupo):

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 

(1, 16), (2, 15), (3, 14), (4, 13), (5, 12), (6, 11), (7, 10), (8, 9) 

(1, 16, 8, 9), (2, 15, 7, 10), (3, 14, 6, 11), (4, 13, 5, 12) 

(1, 16, 8, 9, 4, 13, 5, 12), (2, 15, 7, 10, 3, 14, 6, 11) 

Así que ahora, después de los 8 jugadores de fondo se eliminan, nos quedamos con 1, 8, 4, 5, 2, 7, 3, 6. Después de que se eliminen los 4 de abajo tenemos 1, 4, 2, 3, y en la ronda final solo 1, 2.

Es difícil explicar esto sin poder dibujar un corchete ... Háganme saber si puedo aclarar algo para usted.

Answer 4

Aquí está el algoritmo que he desarrollado.El paso 1 es dibujar una tabla con tantas filas como equipos (redondeados a una potencia de 2) y tantas columnas como sea necesario para representar la cantidad de equipos en binario. Diga, hay 8 equipos. La tabla se verá inicialmente así (los puntos representan los límites de las celdas horizontales):

. . . | | | | . . . | | | | . . . | | | | . . . | | | | . . . | | | | . . . | | | | . . . | | | | . . . | | | | . . .

Las columnas están numeradas desde la izquierda en orden ascendente. Para cada columna ponga un asterisco en cada fila de 2^(número de columna). Es decir, cada 2ª fila en la columna 1, cada 4ª fila en la columna 2, etc.

. . . | | | | . . . | | | | *. . | | | | . . . | | | | * *. | | | | . . . | | | | *. . | | | | . . . | | | |

---

Comience con un 0 en cada columna de la 1ª fila. A partir de entonces, para las filas sucesivas de cada columna, alternar entre 0-1 y 1-0 a menos que haya un asterisco en esa fila. Este es el resultado:

. . . | 0 | 0 | 0 | . . . | 1 | 1 | 1 | *. . | 1 | 0 | 0 | . . . | 0 | 1 | 1 | * *. | 0 | 1 | 0 | . . . | 1 | 0 | 1 | *. . | 1 | 1 | 0 | . . . | 0 | 0 | 1 |

---

El último paso es evaluar cada fila tratando la cadena de 0 y 1 como un número binario. Esto dará como resultado valores de 0-7. Agregar 1 a cada resultado en valores de 1-8. Estos corresponden a las siembras.

. . . | 0 | 0 | 0 | + 1 = 1 . . . | 1 | 1 | 1 | + 1 = 8 *. . | 1 | 0 | 0 | + 1 = 5 . . . | 0 | 1 | 1 | + 1 = 4 * *. | 0 | 1 | 0 | + 1 = 3 . . . | 1 | 0 | 1 | + 1 = 6 *. . | 1 | 1 | 0 | + 1 = 7 . . . | 0 | 0 | 1 | + 1 = 2

---

Cada par de semillas son los partidos que se jugarán en orden. es decir. 1-8, 5-4, 3-6 y 7-2. Esto es extensible a cualquier cantidad de semillas. Cuando se deben insertar byes debido a que el número de entradas es menor que una potencia de 2, toman los valores de semilla más altos. p.ej. si solo había 28 participaciones, entonces byes toman las posiciones asignadas a 29, 30, 31 y 32.

Answer 5

Escribí una solución en PHP (vea https://stackoverflow.com/a/45566890/760777). Aquí está la versión de javascript.

Devuelve todas las semillas en las posiciones correctas. Las coincidencias son las mismas que en su ejemplo, pero en un orden más bonito, la semilla 1 y la semilla número 8 están en el exterior del esquema (como se ve en los torneos de tenis).

Si no hay molestias (lo que significa que un jugador mejor sembrado siempre gana de un jugador con menor preclasificado), terminarás con la semilla 1 contra la semilla 2 en la final.

En realidad, hace dos cosas más:

1. Se muestra el orden correcto (que es un requisito para poner despedidas en las posiciones correctas)

2. Se llena en despedidas en las posiciones correctas (si se requiere)

una explicación perfecta de lo que una sola eliminatoria debe verse como: http://blog.playdriven.com/2011/articles/the-not-so-simple-single-elimination-advantage-seeding/

ejemplo Código de 8 participantes:

var NUMBER_OF_PARTICIPANTS = 8; // Set the number of participants 
 

 
if (!String.prototype.format) { 
 
    String.prototype.format = function() { 
 
    var args = arguments; 
 
    return this.replace(/{(\d+)}/g, function(match, number) { 
 
     return typeof args[number] != 'undefined' ? args[number] : match; 
 
    }); 
 
    }; 
 
} 
 

 
var participants = Array.from({length: NUMBER_OF_PARTICIPANTS}, (v, k) => k + 1) ; 
 
var bracket = getBracket(participants); 
 

 
console.log(bracket); 
 

 
function getBracket(participants) 
 
{ 
 
    var participantsCount = participants.length; \t 
 
    var rounds = Math.ceil(Math.log(participantsCount)/Math.log(2)); 
 
    var bracketSize = Math.pow(2, rounds); 
 
    var requiredByes = bracketSize - participantsCount; 
 
\t 
 
    console.log("Number of participants: {0}".format(participantsCount)); 
 
    console.log("Number of rounds: {0}".format(rounds)); 
 
    console.log("Bracket size: {0}".format(bracketSize)); 
 
    console.log("Required number of byes: {0}".format(requiredByes));  
 
    
 
    if(participantsCount < 2) { 
 
    return []; 
 
    } 
 
    
 
    var matches = [[1,2]]; 
 
    
 
    for(var round = 1; round < rounds; round++) { 
 
    var roundMatches = []; 
 
    var sum = Math.pow(2, round + 1) + 1; 
 
    
 
    for(var i = 0; i < matches.length; i++) { 
 
     var home = changeIntoBye(matches[i][0], participantsCount); 
 
     var away = changeIntoBye(sum - matches[i][0], participantsCount); 
 
     roundMatches.push([home, away]); 
 
     home = changeIntoBye(sum - matches[i][1], participantsCount); 
 
     away = changeIntoBye(matches[i][1], participantsCount); 
 
     roundMatches.push([home, away]); 
 
    } 
 
    matches = roundMatches; 
 
    
 
    } 
 
    
 
    return matches;  
 
} 
 

 
function changeIntoBye(seed, participantsCount) 
 
{ 
 
    //return seed <= participantsCount ? seed : '{0} (= bye)'.format(seed); 
 
    return seed <= participantsCount ? seed : null; 
 
}

Cambio NUMBER_OF_PARTICIPANTS de 8 a 6 para obtener dos despedidas.

Buena suerte. RWC