Алгоритм сортировки для реализации наивысших общих комбинаций

Ответ 1

Для этого вы можете использовать A * algorithm. В качестве эвристической функции возьмите стоимость уже выбранных игроков плюс максимальная стоимость оставшихся игроков, необходимых для завершения команды.

Здесь приведен код Python. Во-первых, настройка:

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]

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

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)

Теперь для интересной части: поиск A *. Мы используем кучу или приоритетную очередь, каждая запись в куче является кортежем (estimated_cost, players, position), поэтому (частичная) команда с самая высокая общая оценочная стоимость будет первой в куче (мы используем -cost, так как куча будет сортироваться от наименьшего к наибольшему). pos сообщает нам нашу текущую позицию в списке игроков, отсортированную по индивидуальной цене, наивысшую первую.

Затем мы выталкиваем следующий элемент из кучи, проверяем, является ли оно решением, и либо yield результат ¹⁾ либо добавляет другого игрока в команду, обновляя сметную стоимость с помощью стоимость текущей команды, пополненная следующими дорогим игроками из основной массы оставшихся игроков (new_players + team_players[i+1:i+more_needed]), и добавьте эту комбинацию в кучу.

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))

Наконец, у нас есть вторая функция-генератор, сопоставляющая вышеприведенные генераторы с именем команды и создающая следующее лучшее решение для каждой команды (если таковая имеется) одна за другой. Другая куча используется для хранения лучших в настоящее время решений для каждой команды, отсортированных по общей стоимости.

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

Теперь просто сгенерируйте и напечатайте первые несколько из этого генератора:

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

Вывод в формате (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)]))

Добавление: О производительности. Для небольших команд, генерирующих все комбинации и подбор лучших, как в Питере ответить, вероятно, действительно "достаточно хорош" и, конечно, намного проще. Однако эта версия, использующая A *, может быть намного быстрее и, возможно, стоит попробовать, если у вас есть более крупные команды или большее количество разных команд, или если вам нужно делать это очень часто. Вот некоторая информация о времени, генерирующая десятку команд, использующих оба алгоритма.

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

Обратите внимание, что это для 1000 итераций, поэтому для одной итерации для обоих алгоритмов потребуется всего несколько миллисекунд. Также обратите внимание, что из-за генеративной природы A *, это намного быстрее, чем меньше комбинаций вам нужно. Для наилучшей комбинации он в шесть раз быстрее, а в первой десятке - в четыре раза быстрее, но если вы хотите все комбинации в любом случае, A * на самом деле в три раза медленнее, чем просто генерирование всех комбинаций в первую очередь.

¹⁾ Обратите внимание, что это использование функций генератора, которые довольно уникальны для Python, но вы можете сделать то же самое, используя класс, инкапсулирующий очередь как член, и предоставляющий метод, возвращающий следующий действительное решение. Если вы заинтересованы, я мог бы также переписать его таким образом.

Ответ 2

Вы можете сортировать игроков в порядке убывания в каждой команде, а затем отсортировать отсортированный список. Код может выглядеть примерно так:

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;
}

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

Ответ 3

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

• Отсортируйте каждую команду в уменьшении значения оценки. Быстрый и простой способ - вставить членов команды в кучу.

• Чтобы найти самую высокую скоринговую комбинацию в каждой команде, поместите кучу 4 раза и добавьте значения этих 4 узлов. Это ваша максимальная комбинация.

Худшая сложность случая - O (n ^ 2).

Чтобы обобщить это на вершину n, поп-верхнюю 3, суммируйте, затем для каждого элемента слева, поместите этот элемент, суммируйте его и вставьте в другую максимальную кучу, чтобы отсортировать этот список. Продолжайте движение вниз по списку, повторяя то же самое для top-1 node в исходной куче.

Ответ 4

Учитывая размер команды 20, в команде есть только 20*19*18*17/(4*3*2*1) = 4845 комбинации из 4 игроков (не все из которых являются законными), поэтому вы должны иметь возможность просто переборщить все возможные комбинации команд, сортировать и выбирать наивысший результат.

Вот пример кода Python, который делает это для вашего примера:

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

Ответ 5

Поиск всех комбинаций в каждой команде, как это предлагает @Peter de Rivaz, безусловно, проще всего сделать правильно. Я включил Ruby-код в качестве основы для тестирования чего-то более сложного.

Но, оказывается, вы можете применить к этой проблеме простой жадный алгоритм. Таким образом, предложения A * и другие поисковые запросы чрезмерны. Холма достаточно. Я все еще не уверен, что это стоит проблемы с размером данных. У меня не будет времени, чтобы закодировать его. Это было бы не очень сложно, но там значительная бухгалтерская отчетность, а крайние случаи (например, игроки и комбинации с точно равными значениями) должны выполняться с осторожностью.

Аргумент для жадности выглядит следующим образом:

ПРЕДЛОЖЕНИЕ: Пусть C = c_0, c_1, ..., c_N-1 - комбинации из 4 игроков, расположенных в порядке убывания суммарного значения. Тогда для каждого 1 <= i < N можно сказать, что c_i может быть сформировано путем принятия некоторого c_j, 0 <= j < i (комбинации более высокого значения) и подстановки ровно одного из четырех его элементов P другим игроком Q минимально более низкое значение. Под минимально низким значением мы подразумеваем, что нет игрока с тем же положением, что и Q, с более высоким значением, которое все еще ниже, чем P.

Доказательство от противного является утомительным, но довольно простым, и я его не дам.

Как превратить это в алгоритм? Фокус в том, что если у нас есть какая-либо комбинация [A, B, C, D], множество возможных "следующих" комбинаций для одной и той же команды в отсортированном порядке невелико. Просто подумайте о замене каждого из комбо-элементов в U = [A, B, C, D] подряд со всеми возможными "законными" игроками, имеющими минимально меньшее значение. Например, пусть следующий (P, pos) будет единственным игроком с позицией pos, имеющим наивысшее значение ниже P. Пусть O - множество всех позиций не в {pos (A), pos (B), pos (C), pos (D)}. Тогда возможные комбинации "преемника" в отсортированном порядке после [A, B, C, D] просто

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)

Таким образом, succ (U) содержит небольшое конечное число элементов. Алгоритм только начинается с комбинации максимального значения для каждой команды, помещает его в очередь приоритетов, затем многократно вытягивает комбинацию из очереди (это вывод), находит своих возможных преемников и добавляет их в очередь. Он сохраняет "посещенный" набор, чтобы предотвратить добавление элемента несколько раз.

Можно показать - хотя я не буду делать этого здесь - что куча будет содержать не более O (n ^ 3) элементов, где n - количество игроков в команде. Таким образом, время выполнения будет равно O (log n) за комбинацию, выведенную из кучи. Вы можете остановиться в любое удобное для вас время.

Вот псевдокод:

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)
}

Извините, у меня нет времени прямо сейчас, чтобы закодировать это. Было бы весело.

Здесь "грубая сила" Ruby code:

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))

Ответ 6

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

Я думаю, что алгоритм Bellman-Ford мог бы работать.

Ответ 7

Если посмотреть на свою проблему и масштаб, который вы указали как максимальный (500), я бы, вероятно, рекомендовал бы алгоритм быстрой сортировки.

Быстрая сортировка (O (n log n )) по существу систематически выполняет итерацию по каждому элементу и помещает отсортированные значения в новый массив. Худший сценарий для быстрого алгоритма сортировки может быть довольно плохим, когда вы попадаете в большие наборы данных, но для вас это будет вопросом секунд, даже в худшем случае O(N^2).

Думая больше, вы можете посмотреть на кучу сортировки. Сорт кучи будет разделять вашу структуру данных на регионы и перемещать вещи из одного региона в другой, начиная с самого высокого уровня. Я использовал бы это только с большим количеством данных, потому что по большей части он медленнее, чем быстрый. Тем не менее, самый медленный, который вы увидите в виде кучи, находится вокруг O(n log n), он намного более последователен.

Джейк - инженер-программист

Ответ 8

Рассмотрим одну команду на мгновение. Поскольку существует около 5000 различных вариантов, но верхний балл, кажется, составляет около 20 (для примеров, которые вы дали), будет много комбинаций, которые дают одинаковый высокий балл, в среднем около 250 комбинаций для каждого балла, Для Торонто самый высокий балл (19) представляется достижимым только одним способом, возможно, 18 достижим одним или несколькими способами, но число будет быстро расти.

Сортировка не имеет столь большого смысла в этом контексте. У вас будут сотни или, может быть, тысячи вариантов с одинаковым счетом, поэтому их сортировка кажется колоссальной тратой времени на компьютер, когда нет критерия, кроме оценки, для того, чтобы ранжировать одну команду выше другой.

Я предлагаю вам перевернуть проблему и спросить: "Сколько и какие комбинации дают мне оценку X с командой Торонто?" Для max (19 в вашем примере) может быть одна комбинация или несколько комбинаций, но для чисел, меньших максимального, вы получите целую кучу.

Скажем, вы пытаетесь собрать команды Торонто со счетом 16. Сначала вы можете поставить игрока 11 в команду. Тогда проблема станет одной из находок выбора из 3 игроков, которая добавит к 10 и будет иметь не более двух OF. Тогда вы можете сказать, что игрок 11 не входит, но игрок 10 должен быть и т.д. Это проблема типа рюкзака, которая может быть решена путем рекурсии (или если у вас много доступного пространства для памяти, подход снизу вверх со столами). Я думаю, что он будет работать быстро, потому что размер выделения невелик. Каков будет приблизительный диапазон N? Если N достаточно мало, вы можете остановиться до того, как вы сгенерируете все комбинации.