sort complexity bubble best algorithms algorithm sorting

algorithm - complexity - Algoritmo de clasificación para implementar las combinaciones totales más altas



sorting algorithms complexity (8)

Considere un solo equipo por un momento. Como hay aproximadamente 5000 selecciones diferentes, pero el puntaje máximo parece ser alrededor de 20 (para los ejemplos que dio), habrá muchas combinaciones que darán el mismo puntaje alto, un promedio de aproximadamente 250 combinaciones para cada puntaje. . Para Toronto, la puntuación más alta (19) parece ser alcanzable de una sola manera, tal vez 18 sea alcanzable de una o varias maneras, pero el número crecerá rápidamente.

La clasificación no tiene mucho sentido en este contexto. Tendrá cientos, o tal vez miles, de selecciones con el mismo puntaje, por lo que clasificarlas parece un desperdicio colosal de tiempo en la computadora cuando no hay otro criterio que el puntaje para clasificar a un equipo más alto que otro.

Le sugiero que cambie el problema y pregunte: "¿Cuántas y qué combinaciones me dan un puntaje de X con el equipo de Toronto?" Para el máximo (19 en tu ejemplo) puede haber una combinación única o un puñado de combinaciones, pero para números menores que el máximo, obtendrás un montón.

Digamos que estás tratando de construir equipos de Toronto con una puntuación de 16. Primero, puedes poner al jugador 11 en el equipo. Entonces el problema se convertiría en encontrar una selección de 3 jugadores que se suma a 10 y tenga como máximo dos OF. Entonces, podría decir que el jugador 11 no está dentro, pero el jugador 10 debe estarlo, etc. Es un problema de tipo mochila que puede resolverse por recursión (o si tiene mucho espacio de memoria disponible, un enfoque de abajo hacia arriba con tablas). Creo que se ejecutaría rápidamente porque el tamaño de la selección es pequeño. ¿Cuál sería el rango aproximado de N? Si N es lo suficientemente pequeño, puedes detenerte mucho antes de generar todas las combinaciones.

Me interesa saber qué algoritmo sería el más adecuado para resolver el siguiente problema. Aquí están los criterios.

Tengo una lista de jugadores. Cada jugador tiene tres atributos.

  • Equipo
  • Valor
  • Posición

Cada equipo tiene aproximadamente 20 jugadores. Digamos que estamos hablando de béisbol aquí y las posiciones son 1B , 2B , 3B , SS , C , OF .

Lo que me interesa hacer es clasificar para las mejores combinaciones de N , donde N > 0 del valor combinado más alto para 4 compañeros de equipo.

Así que cada combinación de 4 players tiene que estar en el mismo equipo. Cada combinación de 4 players debe tener un Value combinado total más alto que cada combinación posterior.

La única restricción es que cada posición se puede usar solo una vez por combinación, excepto por OF que se puede usar hasta tres veces en una combinación de 4 jugadores.

Así que en el siguiente grupo de jugadores inventados, mostraré las 2 mejores combinaciones:

Team Toronto Player 1, SS, 1.0 Player 2, 1B, 1.0 Player 3, 1B, 2.0 Player 4, 2B, 2.0 Player 5, 3B, 4.0 Player 6, 3B, 3.0 Player 7, C, 4.0 Player 8, OF, 1.0 Player 9, OF, 2.0 Player 10, OF, 5.0 Player 11, OF, 6.0 Team Washington Team Toronto Player 1, SS, 3.0 Player 2, 1B, 2.0 Player 3, 1B, 1.0 Player 4, 2B, 2.0 Player 5, 3B, 2.0 Player 6, 3B, 3.0 Player 7, C, 7.0 Player 8, OF, 1.0 Player 9, OF, 2.0 Player 10, OF, 2.0 Player 11, OF, 3.0

El combo proyectado más alto sería

Team Toronto: * Player 11 * Player 10 * Player 7 * Player 5

valor total de 19.0

El segundo combo proyectado más alto también sería Team Toronto con

* Player 11 * Player 10 * Player 7 * Player 6

con un total de 18.0

El combo más alto del Equipo Washington es el Jugador 1, el Jugador 6, el Jugador 7 y el Jugador 11, y su valor es de solo 16.0 por lo que no aparecerán hasta más tarde en el orden.

¿Cuál es el mejor algoritmo para manejar esto de manera eficiente si digo que estoy tratando con un grupo de 500 jugadores diariamente (distribuidos en 10 o más equipos)?

Creo que esto no es tan complicado como crees. Usa un poco de inferencia matemática para simplificar tu problema.

  1. Ordenar cada equipo en valor decreciente puntuación. Una forma rápida y fácil es poner a los miembros del equipo en un montón máximo.

  2. Para encontrar la combinación de puntuación más alta en cada equipo, extraiga el montón 4 veces y sume los valores de esos 4 nodos. Esta es tu combinación máxima.

La complejidad del peor caso es O (n ^ 2).

Para generalizar esto a la parte superior n, resalte la parte superior 3, sume, luego para cada elemento a la izquierda, extraiga ese elemento, sume y pegue otro montón máximo para mantener esta lista ordenada. Continúe hacia abajo en la lista repitiendo lo mismo para el nodo top-1 en el montón original.

Creo que podrías resolver este problema creando un gráfico que represente las posibles combinaciones de jugadores. Luego use un algoritmo que calcule las rutas más cortas para el gráfico y luego ordene las rutas.

Creo que el algoritmo de Bellman-Ford podría funcionar.

Dado un tamaño de equipo de 20, solo hay 20*19*18*17/(4*3*2*1) = 4845 combinaciones de 4 jugadores del equipo (no todos los cuales son legales), por lo que deberías poder simplemente aplica la fuerza bruta a todas las combinaciones de equipos posibles, ordena y selecciona las de mayor puntuación.

Aquí hay un ejemplo de código de Python que hace esto para su ejemplo:

import itertools def f(s): players = [] for x in s.splitlines(): player,pos,score = x.split('','') score=float(score) pos=pos.strip() players.append( (player,pos,score) ) return players teams={} teams[''Toronto''] = f("""Player 1, SS, 1.0 Player 2, 1B, 1.0 Player 3, 1B, 2.0 Player 4, 2B, 2.0 Player 5, 3B, 4.0 Player 6, 3B, 3.0 Player 7, C, 4.0 Player 8, OF, 1.0 Player 9, OF, 2.0 Player 10, OF, 5.0 Player 11, OF, 6.0""") teams[''Washington''] = f("""Player 1, SS, 3.0 Player 2, 1B, 2.0 Player 3, 1B, 1.0 Player 4, 2B, 2.0 Player 5, 3B, 2.0 Player 6, 3B, 3.0 Player 7, C, 7.0 Player 8, OF, 1.0 Player 9, OF, 2.0 Player 10, OF, 2.0 Player 11, OF, 3.0""") def legal(comb): """Test if this is a legal team combination""" count_of = 0 S = set() for player,pos,score in comb: if pos == ''OF'': count_of += 1 elif pos in S: return False else: S.add(pos) return count_of <= 3 A = [] # List of legal combinations for team_name,players in teams.items(): for comb in itertools.combinations(players,4): if legal(comb): score = sum(p[2] for p in comb) A.append( (score,comb,team_name) ) A.sort(reverse = True) for score,comb,team_name in A[:2]: print score,team_name,comb

Encontrar todas las combinaciones dentro de cada equipo como lo sugiere @Peter de Rivaz es ciertamente el más fácil de hacer correctamente. Incluí el código Ruby como punto de referencia para probar algo más sofisticado.

Pero resulta que puede aplicar un algoritmo codicioso simple a este problema. Así que el A * y otras proposiciones de búsqueda son excesivas. La escalada es suficiente. Todavía no estoy seguro de que valga la pena el problema con el tamaño de sus datos. No tendré tiempo para codificarlo. Eso no sería muy difícil, pero hay una contabilidad significativa, y los casos de ventaja (como jugadores y combinaciones con valores exactamente iguales) deben manejarse con cuidado.

El argumento a favor de la codicia es el siguiente:

Proposición: Sean C = c_0, c_1, ..., c_N-1 las combinaciones de 4 jugadores organizados en orden decreciente de valor total. Luego, para cada 1 <= i < N , podemos decir que c_i puede formarse tomando algunos c_j , 0 <= j < i (una combinación de mayor valor) y sustituyendo exactamente uno de sus cuatro elementos P con un jugador diferente Q de valor mínimamente inferior . Por valor mínimamente más bajo queremos decir que no hay ningún jugador con la misma posición que Q con un valor más alto que aún sea más bajo que P.

La prueba por contradicción es tediosa, pero bastante simple y no la daré.

¿Cómo convertir esto en un algoritmo? El truco es que si tenemos alguna combinación [A, B, C, D], el conjunto de posibles "próximas" combinaciones para el mismo equipo en orden ordenado es pequeño. Simplemente considere reemplazar cada uno de los elementos combinados en U = [A, B, C, D] en sucesión con todos los posibles jugadores "legales" que tengan un valor mínimamente inferior. Por ejemplo, sea siguiente (P, pos) el jugador único con la posición pos con el valor más alto menor que P. Sea O el conjunto de todas las posiciones que no estén en {pos (A), pos (B), pos (C), pos (RE)}. Entonces, las posibles combinaciones de "sucesor" en orden ordenadas después de [A, B, C, D] son ​​solo

succ(U) = next(A, pos(A)) union_(o/in O).next(A, o) union next(B, pos(B)) union_(o/in O).next(B, o) union next(C, pos(C)) union_(o/in O).next(C, o) union next(D, pos(D)) union_(o/in O).next(D, o)

Así que succ (U) contiene un pequeño número finito de elementos. El algoritmo simplemente comienza con la combinación de valor máximo para cada equipo, lo coloca en una cola de prioridad, luego saca una combinación repetidamente de la cola (esta es la salida), encuentra sus posibles sucesores y los agrega a la cola. Mantiene un conjunto "visitado" para evitar agregar un elemento varias veces.

Es posible demostrar, aunque no lo haré aquí, que el montón tendrá un máximo de O (n ^ 3) elementos, donde n es el número de jugadores en un equipo. Por lo tanto, el tiempo de ejecución será O (log n) por combinación extraída del montón. Puedes parar en el momento que quieras.

Aquí está el pseudocódigo:

Let H be a priority queue with add and deleteMax operations. for each team t P = sequence of players of t sorted in decreasing order of value Let Cmax = {} # the maximum value combination for team t. for each player p in P if adding p to Cmax doesn''t make it an invalid combo, add p to Cmax if |Cmax| == 4, break end for # Cmax is now the max value combination for t add Cmax to H end for # H is now initialized with the max val player of each team Let V = {} # A set of visited combinations while H is not empty let c = H.deleteMax output c Add succ(c) - V to H V = V union succ(c) }

Lo siento, no tengo tiempo ahora para codificar esto. Sería divertido.

Aquí está el código de Ruby "fuerza bruta":

Player = Struct.new(''Player'', :team, :name, :pos, :val) # The algorithm. def sorted_combos(data) data.map{|team| team.combination(4).select{|g| combination_ok? g } } .flatten(1).sort_by{|x| x.map(&:val).inject(&:+) }.reverse! end # Checking that a particular combination meets the membership rules. def combination_ok?(g) not_of = g.map(&:pos).select{|x| x != ''OF''} not_of.size >= 1 && not_of.uniq.size == not_of.size end # Test. def parse(teams) teams.map{|t| t[1].split("/n").map{|x| x.split(/,/s*/) } .map{|x| Player.new(t[0], x[0], x[1], x[2].to_f) } } end DATA = [ [''Toronto'', ''Player 1, SS, 1.0 Player 2, 1B, 1.0 Player 3, 1B, 2.0 Player 4, 2B, 2.0 Player 5, 3B, 4.0 Player 6, 3B, 3.0 Player 7, C, 4.0 Player 8, OF, 1.0 Player 9, OF, 2.0 Player 10, OF, 5.0 Player 11, OF, 6.0'' ], [''Washington'', ''Player 1, SS, 3.0 Player 2, 1B, 2.0 Player 3, 1B, 1.0 Player 4, 2B, 2.0 Player 5, 3B, 2.0 Player 6, 3B, 3.0 Player 7, C, 7.0 Player 8, OF, 1.0 Player 9, OF, 2.0 Player 10, OF, 2.0 Player 11, OF, 3.0'' ], ] print sorted_combos(parse(DATA))

Mirando su problema y la escala de la que ha indicado que es un máximo (500), probablemente recomendaría un algoritmo de clasificación rápida.

La ordenación rápida ( O (n log n ) ) esencialmente repite sistemáticamente sobre cada elemento y coloca los valores ordenados en una nueva matriz. El peor escenario para un algoritmo de clasificación rápida puede ser bastante malo cuando se ingresa en conjuntos de datos grandes, pero para el suyo sería cuestión de segundos, incluso en el peor de los casos O(N^2) .

Pensando en grande, podrías mirar una especie de montón. Una clasificación de pila dividirá su estructura de datos en regiones y moverá las cosas de una región a otra, comenzando por la más alta primero. Solo usaría esto con grandes cantidades de datos, porque en su mayor parte es más lento que una clasificación rápida. Sin embargo, lo más lento que verás en una clasificación de pila es alrededor de O(n log n) , es mucho más consistente.

Jake - Ingeniero de Software

Puedes clasificar a los jugadores en orden decreciente en cada equipo y luego repetir la lista ordenada de tiros. El código puede verse algo como esto:

int highestCombinedValue = 0, i = 0, currentNumber = 0, count1B = 0, count2B = 0, cpunt3B = 0, countSS =0, countC = 0, countOF = 0; while(currentNumber < 4 && list.get(i) != null) { currentPlayer = list.get(i); switch currentPlayer.position { case: 1B then if(count1B < 1) { highestCombinedValue = highestCombinedValue + currentPlayer.value; count1B = count1B + 1; } break; case: 2B ... case: OF then if(count1B < 3) { highestCombinedValue = highestCombinedValue + currentPlayer.value; count1B = count1B + 1; } break; } i = i + 1; }

Puede almacenar el equipo con el resultado en la lista y ordenar esta lista de resultados en orden decreciente para obtener los mejores equipos.

Puedes usar el algoritmo A * para esto. Como función heurística, tome el costo de los jugadores ya seleccionados más el costo máximo de los jugadores restantes necesarios para completar el equipo.

Aquí hay un código de Python. Primero, la configuración:

def split(team): return [(x.strip(), y.strip(), float(z)) for x, y, z in (line.split(",") for line in team.splitlines())] team1 = ("Toronto", split("""Player 1, SS, 1.0 Player 2, 1B, 1.0 Player 3, 1B, 2.0 Player 4, 2B, 2.0 Player 5, 3B, 4.0 Player 6, 3B, 3.0 Player 7, C, 4.0 Player 8, OF, 1.0 Player 9, OF, 2.0 Player 10, OF, 5.0 Player 11, OF, 6.0""")) team2 = ("Washington", split("""Player 1, SS, 3.0 Player 2, 1B, 2.0 Player 3, 1B, 1.0 Player 4, 2B, 2.0 Player 5, 3B, 2.0 Player 6, 3B, 3.0 Player 7, C, 7.0 Player 8, OF, 1.0 Player 9, OF, 2.0 Player 10, OF, 2.0 Player 11, OF, 3.0""")) teams = [team1, team2]

También necesitamos una función para saber si una combinación determinada es válida. No necesitamos verificar que ningún jugador aparezca dos veces, ya que serán únicos por construcción, así que solo tenemos la frecuencia con la que aparecen las posiciones de cada jugador.

ALLOWED = {"1B": 1, "2B": 1, "3B": 1, "SS": 1, "C": 1, "OF": 3} def legal(players): d = {} for p in players: d[p[1]] = d.get(p[1], 0) + 1 return all(d[x] <= ALLOWED[x] for x in d)

Ahora para la parte interesante: La búsqueda A *. Estamos utilizando un montón, o cola de prioridad , cada entrada en el montón es una tupla (estimated_cost, players, position) costo (estimated_cost, players, position) , por lo que el equipo (parcial) con el costo total estimado más alto será el primero en el montón (usamos -cost , como el montón se ordenará de menor a mayor). pos nos dice nuestra posición actual en la lista de jugadores, ordenados por costo individual, primero el más alto.

Luego sacamos el siguiente elemento del montón, verificamos si es una solución y yield el resultado 1) , o agregamos otro jugador al equipo, actualizando el costo estimado con el costo del equipo actual, llenado con el siguiente jugadores caros de la mayoría de los jugadores restantes ( new_players + team_players[i+1:i+more_needed] ), y agregue esa combinación al montón.

def generator(team_players, num): team_players = sorted(team_players, key=lambda p: p[2], reverse=True) queue = [(-sum(p[2] for p in team_players[:num]), [], 0)] while queue: estimated_cost, players, pos = heapq.heappop(queue) more_needed = num - len(players) if not more_needed: yield estimated_cost, players else: for i in range(pos, len(team_players) - more_needed + 1): player = team_players[i] new_players = players + [player] if legal(new_players): estimate = -sum(p[2] for p in new_players + team_players[i+1:i+more_needed]) heapq.heappush(queue, (estimate, new_players, i+1))

Finalmente, tenemos una segunda función de generador, asignando los generadores anteriores al nombre del equipo y generando la mejor solución para cada equipo (si corresponde) uno tras otro. Otro montón se utiliza para almacenar las mejores soluciones actualmente para cada equipo, ordenadas por costo total.

def generate_all(teams): generators = {name: generator(players, 4) for name, players in teams} best_teams = [(next(generators[name]), name) for name in generators] heapq.heapify(best_teams) while best_teams: team, name = heapq.heappop(best_teams) yield name, team try: heapq.heappush(best_teams, (next(generators[name]), name)) except StopIteration: pass

Ahora solo genera e imprime los primeros de ese generador:

all_teams_generator = generate_all(teams) for _ in range(10): print(next(all_teams_generator))

Salida en formato (team-name, (-cost, [(player1), ..., (player4)])) :

(''Toronto'', (-19.0, [(''Player 11'', ''OF'', 6.0), (''Player 10'', ''OF'', 5.0), (''Player 5'', ''3B'', 4.0), (''Player 7'', ''C'', 4.0)])) (''Toronto'', (-18.0, [(''Player 11'', ''OF'', 6.0), (''Player 10'', ''OF'', 5.0), (''Player 7'', ''C'', 4.0), (''Player 6'', ''3B'', 3.0)])) (''Toronto'', (-17.0, [(''Player 11'', ''OF'', 6.0), (''Player 10'', ''OF'', 5.0), (''Player 5'', ''3B'', 4.0), (''Player 3'', ''1B'', 2.0)])) (''Toronto'', (-17.0, [(''Player 11'', ''OF'', 6.0), (''Player 10'', ''OF'', 5.0), (''Player 5'', ''3B'', 4.0), (''Player 4'', ''2B'', 2.0)])) (''Toronto'', (-17.0, [(''Player 11'', ''OF'', 6.0), (''Player 10'', ''OF'', 5.0), (''Player 5'', ''3B'', 4.0), (''Player 9'', ''OF'', 2.0)])) (''Toronto'', (-17.0, [(''Player 11'', ''OF'', 6.0), (''Player 10'', ''OF'', 5.0), (''Player 7'', ''C'', 4.0), (''Player 3'', ''1B'', 2.0)])) (''Toronto'', (-17.0, [(''Player 11'', ''OF'', 6.0), (''Player 10'', ''OF'', 5.0), (''Player 7'', ''C'', 4.0), (''Player 4'', ''2B'', 2.0)])) (''Toronto'', (-17.0, [(''Player 11'', ''OF'', 6.0), (''Player 10'', ''OF'', 5.0), (''Player 7'', ''C'', 4.0), (''Player 9'', ''OF'', 2.0)])) (''Toronto'', (-16.0, [(''Player 11'', ''OF'', 6.0), (''Player 10'', ''OF'', 5.0), (''Player 5'', ''3B'', 4.0), (''Player 1'', ''SS'', 1.0)])) (''Toronto'', (-16.0, [(''Player 11'', ''OF'', 6.0), (''Player 10'', ''OF'', 5.0), (''Player 5'', ''3B'', 4.0), (''Player 2'', ''1B'', 1.0)]))

Anexo: Sobre el rendimiento. Para equipos pequeños, generar todas las combinaciones y elegir las mejores, como en la respuesta de Peter , es probablemente "suficientemente bueno", y ciertamente mucho más simple. Sin embargo, esta versión, que usa A *, puede ser mucho más rápida y podría valer la pena probarla si tiene equipos más grandes, o una mayor cantidad de equipos diferentes, o si tiene que hacerlo muy a menudo. Aquí hay algo de información de tiempo, generando los diez mejores equipos usando ambos algoritmos.

>>> timeit.timeit("allcomb.main(10)", "import allcomb", number=1000) 6.20834589005 >>> timeit.timeit("astar.main(10)", "import astar", number=1000) 1.55367398262

Tenga en cuenta que esto es para 1000 iteraciones, por lo que para una sola iteración, ambos algoritmos necesitarán solo unos pocos milisegundos. También tenga en cuenta que debido a la naturaleza generativa del A *, es mucho más rápido cuantas menos combinaciones necesite. Solo para la mejor combinación, es seis veces más rápido, y para los diez primeros, es cuatro veces más rápido, pero si quieres todas las combinaciones de todos modos, el A * es de hecho tres veces más lento que generar todas las combinaciones en primer lugar .

1) Tenga en cuenta que esto es mediante el uso de funciones generadoras, que son bastante exclusivas de Python, pero puede hacer lo mismo usando una clase que encapsula la cola como miembro y proporciona un método, devolviendo la siguiente solución válida. Si estás interesado, también podría reescribirlo de esa manera.