If you want to do 400 players and not do anything to reduce cull the list (remove players with low scores and/or poor value) you can get a supercomputer.
Memory is not a problem. You are probably making a list to hold all the teams. Instead, you should do one team at a time. Itertools.combinations is a lazy iterator and generates combinations when requested.
Pseudo code:
best_team = None
for team in itertools.combinations(players, 5):
if team.cap_score <= 120:
if best_team is None or best_team.score < team.score:
best_team = team
print(best_team)That fixes the memory problems, but you still have the time problems. I was playing around measuring times for different numbers of players,
30 players = 0.27 seconds
40 players = 1.38 seconds
50 players = 4.52 seconds
60 players = 11.59 seconds
70 players = 26.55 seconds
400 players = 53 hours (estimated)
The easiest way to speed things up is reduce the number of players. Ignore players scoring under the league average and or players that have a low score/average value.
But even if you threw away 200 players, you would still have 200 players to evaluate. Extrapolating from my tests I would expect it to take about 1.6 hours to find the best team that could be made from a pool of 200 players.
You might be able to speed things up by reducing the player list as you are building the team. This is a recursive solution that skips players a team cannot afford. Depending on how early in the search you skip a player this can prevent having to test thousands of teams that don't fit under the cap.
from random import randint
from time import time
class Player:
"""Player info"""
def __init__(self, id):
self.id = id
self.avg = randint(0, 100)
self.score = max(0, self.avg +randint(-50, 50))
def __str__(self):
return self.__repr__()
def __repr__(self):
return f'{self.id} avg={self.avg} score={self.score}'
class Team:
"""A team with 5 players."""
def __init__(self):
self._players = []
self.score = 0
self.cap = 120
def __str__(self):
return self.__repr__()
def __repr__(self):
players = '\n'.join(str(p) for p in self._players)
return f'{players}\ncap={self.cap} score={self.score}\n'
def push(self, player):
"""Add player to the roster"""
if self._players:
self.cap -= player.avg
self.score += player.score
self._players.append(player)
def pop(self):
"""Remove last player added to the roster"""
player = self._players.pop()
if self._players:
self.cap += player.avg
self.score -= player.score
def complete(self):
"""Return True if team has all 5 players"""
return len(self.players) >= 5
@property
def players(self):
"""Return list of players"""
return self._players
@players.setter
def players(self, roster):
"""Set list of players"""
self._players[:] = roster
self.cap = 120 - sum(p.avg for p in roster[1:])
self.score = sum(p.score for p in roster)
def get_best_team(players, index=0, team=None, best_team=None):
"""Find the best combination of 5 players that falls under the cap"""
if team is None:
team = Team()
best_team = Team()
get_best_team.counter = 0
if team.complete():
# Is this the best team so far?
get_best_team.counter += 1
if team.score > best_team.score:
best_team.players = team.players
return best_team
for i in range(index, len(players)):
if players[i].avg <= team.cap:
team.push(players[i])
get_best_team(players, i+1, team, best_team)
team.pop()
return best_team
# Sort players so most expensive (avg) are first.
players = sorted([Player(i) for i in range(1, 61)], key=lambda p:p.avg, reverse=True)
start = time()
print(get_best_team(players))
print(time() - start, get_best_team.counter)I ran some tests comparing computing combinations and using the recursive looping function. Time is in seconds.
Output:
#Teams Comb Time Loop Time
40 1.38 0.11
50 4.52 0.44
60 11.59 0.75
70 26.55 1.75
80 67.20 3.58
Timing is less deterministic using this approach, but a very rough estimate for creating teams with a pool of 200 players is 6.3 minutes, and 3.5 hours for a pool of 400 players. When I wrote the program in C it takes under 5 minutes to solve for a pool of 400 players.
In case you were wondering how loops can replace combinations, just take a look at the combinations generated here:
from itertools import combinations
print(list(combinations((1, 2, 3, 4), 2)))
Output:
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
And the output from this program:
def combinations(numbers, index=0, combo=None, combos=None):
if combo is None:
combo = []
combos = []
if len(combo) >= 2:
combos.append(combo.copy())
return combos
for i in range(index, len(numbers)):
combo.append(numbers[i])
combinations(numbers, i+1, combo, combos)
combo.pop()
return combos
print(combinations((1, 2, 3, 4)))Output:
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
