0
200
ViewsAlgoritmo para un generador de equipos.
Creé un generador de equipos aleatorios con Javascript y funciona para generar dos equipos aleatorios de cinco jugadores cada uno. Así es como se ve: 
y creé una función para determinar el valor de cada rango:
function getRankValue(rank) { let rankValue; switch(rank) { case "platinum1" : rankValue = 2100; break; case "platinum2" : rankValue = 2000; break; case "platinum3" : rankValue = 1900; break; case "platinum4" : rankValue = 1800; break; case "gold1" : rankValue = 1650; break; case "gold2" : rankValue = 1550; break; case "gold3" : rankValue = 1450; break; case "gold4" : rankValue = 1350; break; case "silver1" : rankValue = 1200; break; case "silver2" : rankValue = 1100; break; case "silver3" : rankValue = 1000; break; case "silver4" : rankValue = 900; break; case "bronze1" : rankValue = 750; break; case "bronze2" : rankValue = 650; break; case "bronze3" : rankValue = 550; break; case "bronze4" : rankValue = 450; break; case "iron1" : rankValue = 300; break; case "iron2" : rankValue = 200; break; case "iron3" : rankValue = 100; break; case "iron4" : rankValue = 0; break; } return rankValue;Quiero hacer que el generador cree equipos en función del valor de rango de los jugadores para crear un valor de equipo total equilibrado. Por ejemplo :
4x Silver4 (valor 900 cada uno) y 1x bronce 4 (valor 450) por un valor total de 4050 versus:
3x Silver1 (valor de 1200 cada uno) y 2x iron2 (valor de 200 cada uno) por un valor total de 4000. Quiero que tenga espacio para un valor de +- 200, de lo contrario sería demasiado complejo.
¿Cómo debería ser el algoritmo?
1 answers
Answer question0
Aquí hay una solución basada en generar todas las combinaciones. Tenga en cuenta que la partición de números equilibrados y la partición de dos vías tienen varias soluciones prácticas. La solución presentada aquí hace uso de una evaluación de fuerza bruta de todas las combinaciones de 5 jugadores.
Usando una función de combinación de python como referencia, la versión Javascript de la siguiente función de iterador de combinations produce combinaciones de 5 jugadores de la lista provista de clasificaciones de 10 jugadores. La solución general es la fuerza bruta, ya que itera sobre todas las combinaciones de 5 jugadores y devuelve la mejor combinación de jugadores en función de la menor diferencia en los valores del equipo.
function *combinations( combo, list, k ) { if ( k == 0 ) { yield combo; } else { for ( let i = 0; i < list.length; i++ ) { yield *combinations( [...combo, list[ i ] ], list.slice( i + 1 ), k - 1 ); } } } let players = [ 1200, 1200, 1200, 900, 900, 900, 900, 450, 200, 200 ]; let playersTotal = players.reduce( ( sum, player ) => sum += player, 0 ); let team1 = combinations( [], players, 5 ); let nextCombo; let minCombo, minDiff = Number.MAX_SAFE_INTEGER; do { nextCombo = team1.next().value; if ( nextCombo == null ) break; let team1Sum = nextCombo.reduce( ( sum, player ) => sum += player, 0 ); let diff = Math.abs( ( playersTotal - team1Sum ) - team1Sum ); if ( diff < minDiff ) { minCombo = nextCombo; minDiff = diff; } if ( diff <= 200 ) { console.log( `Team: ${nextCombo.join( ',' )}, Total: ${team1Sum}, Diff: ${diff}` ); } } while ( true ); console.log( `Best matchup is Team 1 of ${minCombo} with diff of ${minDiff}` ); Tenga en cuenta que el uso de una función de iterador para generar combinaciones tiene la ventaja de finalizar la solicitud de más combinaciones si está satisfecho con el resultado más reciente. Esto también tiene la ventaja de que, si se buscan equipos más grandes, donde calcular todas las combinaciones no es práctico, se puede agregar un temporizador al ciclo que busca la siguiente combinación del equipo, y se puede usar el mejor resultado después de que se acabe el tiempo, de modo que limitar el tiempo de búsqueda. En tal caso, será prudente barajar aleatoriamente la lista de jugadores antes de llamar a las combinations para que las combinaciones generadas no estén todas cargadas con los mejores jugadores, dando una mejor oportunidad de obtener un emparejamiento equilibrado de equipos...