статистический анализ питона

Question

Учитывая 15 игроков - 2 вратаря, 5 защитников, 5 полузащитников и 3 нападающих, а также тот факт, что у каждого есть ценность и результат, я хочу подсчитать наивысшую результативную команду из имеющихся у меня денег.Каждая команда должна состоять из 1 ГК, затем формирования, например, 4: 4: 2, 4: 3: 3 и т. Д. Я начал с выборочных данных, таких как

ролевые очки игрока, стоимость

I тогдапроделал следующее, чтобы оценить все комбинации

прочитать каждую строку в список (для каждой роли), затем использовать itertools во вложенном прогоне, чтобы получить все комбинации

if line[1] == "G": G.append(line[0])
if line[1] == "D": D.append(line[0])
if line[1] == "M": M.append(line[0])
if line[1] == "S": S.append(line[0])

for gk in itertools.combinations(G,1):
    for de in itertools.combinations(D,4):
        for mi in itertools.combinations(M,4):
            for st in itertools.combinations(S,2):
                teams[str(count)]= " ".join(gk)+" "+" ".join(de)+" "+" ".join(mi)+" "+" ".join(st)
                count +=1

Получив команды, ярассчитать стоимость их очков и стоимость команды.Если он ниже порогового значения, я его распечатываю.
Но если я сейчас сделаю это 20 вратарей, 150 защитников, 150 полузащитников и 100 нападающих, то вполне понятно, что мне не хватает памяти.
Что я могу сделать, чтобы выполнить этот анализ?Мне нужен генератор, а не рекурсивная функция?

Большое спасибо

Answer 1

Вы можете решить эту проблему с помощью рекурсии. Ниже показан основной план, но игнорируются такие детали, как команда, состоящая из определенного количества игроков определенного типа.

players=[{'name':'A','score':5,'cost':10},
         {'name':'B','score':10,'cost':3},
         {'name':'C','score':6,'cost':8}]

def player_cost(player):
    return player['cost']
def player_score(player):
    return player['score']
def total_score(players):
    return sum(player['score'] for player in players)

def finance_team_recurse(budget, available_players):
    affordable_players=[]
    for player in available_players:
        if player_cost(player)<=budget:
            # Since we've ordered available players, the first player appended
            # will be the one with the highest score.
            affordable_players.append(player)
    result=[]
    if affordable_players:
        candidate_player=affordable_players[0]
        other_players=affordable_players[1:]
        # if you include candidate_player on your team
        team_with_candidate=finance_team_recurse(budget-player_cost(candidate_player),
                                                 other_players)
        team_with_candidate.append(candidate_player)
        score_of_team_with_candidate=total_score(team_with_candidate)
        if score_of_team_with_candidate>total_score(other_players):
            result=team_with_candidate
        else:
            # if you exclude candidate_player from your team
            team_without_candidate=finance_team_recurse(budget, other_players)
            score_of_team_without_candidate=total_score(team_without_candidate)
            if score_of_team_with_candidate>score_of_team_without_candidate:
                result=team_with_candidate
            else:
                result=team_without_candidate
    return result

def finance_team(budget, available_players):
    tmp=available_players[:]
    # Sort so player with highest score is first. (Greedy algorithm?)
    tmp.sort(key=player_score, reverse=True)
    return finance_team_recurse(budget,tmp)

print(finance_team(20,players))
# [{'score': 6, 'cost': 8, 'name': 'C'}, {'score': 10, 'cost': 3, 'name': 'B'}]

---

20 choose 1 = 20 combinations
150 choose 4 = 20260275 combinations
100 choose 2 = 4950 combinations

Таким образом, в общей сложности 20 * 20260275 * 20260275 * 4950 = 40637395564486875000L предметы в teams дикт. Это занимает много памяти.

for gk in itertools.combinations(G,1):
    for de in itertools.combinations(D,4):
        for mi in itertools.combinations(M,4):
            for st in itertools.combinations(S,2):    
                #Don't collect the results into a dict.
                #That's what's killing you (memory-wise).
                #Just compute the cost and
                #Just print the result here.

PS. 40637395564486875000L - порядка 10**19. Предполагая, что ваша программа может обрабатывать 10**6 комбинаций в секунду, для завершения программы потребуется около 1,3 миллиона лет ...

Answer 2

Функции и генераторы очень помогают:

def make_teams(G, D, M, S):
    """ returns all possible teams """
    for gk in itertools.combinations(G,1):
        for de in itertools.combinations(D,4):
            for mi in itertools.combinations(M,4):
                for st in itertools.combinations(S,2):
                    yield gk, de, mi, st

def get_cost( team ):
    return sum( member.cost for member in team )

def good_teams( min_score=0):
    for team in make_teams(G, D, M, S):
        if get_cost( team ) > min_score:
            yield team

for team in good_teams(min_score=100):
    print team

Он по-прежнему генерирует все возможные комбинации, так что вам, вероятно, не хватит времени вместо памяти.

То, что вы делаете, похоже на вариацию задачи о ранце - вы можете сделать лучше, чем попробовать все возможные комбинации, но не намного лучше .

Один из способов быстро найти хорошее решение - отсортировать игроков по их счету за деньги . Сначала вы должны получить лучшие команды, но нет никаких гарантий, что вы получите лучшее из возможных решений. Википедия называет это «алгоритмом жадного приближения».

def score_per_cost( player ):
    return player.score / player.cost

def sorted_combinations(seq, n):
    return itertools.combinations(
        sorted(seq, key=score_per_cost, reverse=True),n)

def make_teams(G, D, M, S):
    """ returns all possible teams """
    for gk in sorted_combinations(G,1):
        for de in sorted_combinations(D,4):
            for mi in sorted_combinations(M,4):
                for st in sorted_combinations(S,2):
                    yield gk, de, mi, st

def get_cost( team ):
    return sum( member.cost for member in team )

def top_teams(n):
    return itertools.islice(make_teams(G, D, M, S),n)

for team in top_teams(100):
    print team

Я оставлю добавление читателю требования «стоимость на команду <порог» (подсказка: это одна строка в <code>make_teams: p).