Комбинация игроков волейбола

Некоторые сведения:
В волейболе игроки играют в пулах для определения ранжирования. Команды - это пары игроков. Матчи - это пара игроков против другой пары игроков. В этом примере давайте предположим, что существует только один суд, в котором можно сыграть матч, а когда игрок не играет, они сидят/ждут. Количество игроков в пуле будет между 4 и 7. Если в пуле есть 8 игроков, они просто разломят его на 2 пула 4.

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

Например, у пула 4 игрока будут следующие команды:

import itertools
players = [1,2,3,4]
teams = [t for t in itertools.combinations(players,2)]
print 'teams:'
for t in teams:
    print t

Выходы:

teams:
(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)

и количество совпадений:

matches = []
for match in itertools.combinations(teams,2):
    # A player cannot be on both teams at the same time
    if set(match[0]) & set(match[1]) == set():
        matches.append(match)

for match in matches:
    print match

Выходы:

((1, 2), (3, 4))
((1, 3), (2, 4))
((1, 4), (2, 3))

Что правильно, но этот алгоритм ломается, когда я добавляю пятого игрока в пул:

((1, 2), (3, 4))
((1, 2), (3, 5))
((1, 2), (4, 5))
((1, 3), (2, 4))
((1, 3), (2, 5))
((1, 3), (4, 5))
((1, 4), (2, 3))
((1, 4), (2, 5))
((1, 4), (3, 5))
((1, 5), (2, 3))
((1, 5), (2, 4))
((1, 5), (3, 4))
((2, 3), (4, 5))
((2, 4), (3, 5))
((2, 5), (3, 4))

Команды дублируются несколько раз.

Я пытался сохранить список команд, которые играют, но этот алгоритм оказывается жадным. Под этим я подразумеваю, что когда он добирается до (1,5) команды, все остальные команды [(2,3), (2,4), (3,4)] уже играют и (1,5) никогда не получают играть.

Что я ищу:

((1,2), (3,4)) (player 5 waits)
((1,3), (2,5)) (player 4 waits)
((1,4), (3,5)) (player 2 waits)
((1,5), (4,2)) (player 3 waits)
((2,3), (4,5)) (player 1 waits)

Было бы проще просто вычислить это вручную для каждого размера пула, или это можно легко сделать в python?

Спасибо за помощь!

Редактировать: Удален тег Python. Любой язык будет достаточным, и я могу преобразовать его в Python.

Ответ 1

Резюме:

Несмотря на свое сходство с NP-полной проблемой минимального набора покрытий, этот вопрос далек от неразрешимости. В частности - и в отличие от минимального набора обложки - мы знаем нетривиальный наилучший возможный ответ заранее.
Этот ответ - количество команд, разделенных на 2 (плюс 1, когда N команд странно). Мы никогда не сможем сделать лучше.
Из-за структуры проблемы существует много приемлемых решений, которые обеспечивают наилучший ответ. Вы можете наткнуться на них, используя базовый рандомизированный жадный алгоритм. По мере того, как N команд растет, ваша первая случайная попытка почти всегда успешна.
Этот подход выполняется даже для большого количества команд (например, всего за пару секунд для 1000 команд).

Детали:

Вы можете использовать формулу для k-комбинаций, чтобы определить количество требуемых команд, чтобы каждый игрок был сопряжен с каждым другим игроком (с k = 2).

n_teams = n! / ( (n - k)! k! )

n     n_teams
--    --------
4     6
5     10
6     15
7     21
8     28
9     36
10    45
11    55      # n_teams always equals the sum of values in previous row

Как насчет минимального количества матчей? Я думаю, что просто n_teams делится на 2 (с некоторым дополнением для обработки нечетного числа команд).

min_n_matches = (n_teams + (n_teams % 2)) / 2

У меня нет строгого доказательства для этого, но интуиция кажется звуковой. Каждый раз, когда вы добавляете нового игрока, вы можете думать об этом как о дополнительном ограничении: вы только что добавили еще одного игрока, который не может появляться с обеих сторон заданного матча. В то же время этот новый игрок создает кучу новых комбинаций команд. Эти новые команды похожи на анти-ограничения: их присутствие облегчает формирование правильных совпадений.

Как видно из приведенной выше формулы и таблицы данных, ограничения (n) растут линейно, но анти-ограничения (n_teams) растут намного быстрее.

Если это так, вам не нужен интеллектуальный алгоритм для решения проблемы: самый жадный, самый умеренный алгоритм будет работать нормально. Сопоставьте команды случайным образом (но верно), и если ваша первая попытка не удалась, попробуйте еще раз. По мере того, как количество команд становится больше, вы редко будете терпеть неудачу с первой попытки.

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

import sys
import itertools
import random

def main():
    maxN = int(sys.argv[1])
    for n in range(4, maxN + 1):
        run_scenario(n)

def run_scenario(n):
    # Takes n of players.
    # Generates matches and confirms our expectations.
    k = 2
    players = list(range(1, n + 1))
    teams   = list(set(t) for t in itertools.combinations(players, k))

    # Create the matches, and count how many attempts are needed.
    n_calls = 0
    matches = None
    while matches is None:
        matches = create_matches(teams)
        n_calls += 1

    # Print some info.
    print dict(
        n       = n,
        teams   = len(teams),
        matches = len(matches),
        n_calls = n_calls,
    )

    # Confirm expected N of matches and that all matches are valid.
    T = len(teams)
    assert len(matches) == (T + (T % 2)) / 2
    for t1, t2 in matches:
        assert t1 & t2 == set()

def create_matches(teams):
    # Get a shuffled copy of the list of teams.
    ts = list(teams)
    random.shuffle(ts)

    # Create the matches, greedily.
    matches = []
    while ts:
        # Grab the last team and the first valid opponent.
        t1 = ts.pop()
        t2 = get_opponent(t1, ts)
        # If we did not get a valid opponent and if there are still
        # teams remaining, the greedy matching failed.
        # Otherwise, we must be dealing with an odd N of teams.
        # In that case, pair up the last team with any valid opponent.
        if t2 is None:
            if ts: return None
            else:  t2 = get_opponent(t1, list(teams))
        matches.append((t1, t2))

    return matches

def get_opponent(t1, ts):
    # Takes a team and a list of teams.
    # Search list (from the end) until it finds a valid opponent.
    # Removes opponent from list and returns it.
    for i in xrange(len(ts) - 1, -1, -1):
        if not t1 & ts[i]:
            return ts.pop(i)
    return None

main()

Образец вывода. Обратите внимание, как количество вызовов очень быстро стремится к 1.

> python volleyball_matches.py 100
{'matches': 3, 'n_calls': 1, 'teams': 6, 'n': 4}
{'matches': 5, 'n_calls': 7, 'teams': 10, 'n': 5}
{'matches': 8, 'n_calls': 1, 'teams': 15, 'n': 6}
{'matches': 11, 'n_calls': 1, 'teams': 21, 'n': 7}
{'matches': 14, 'n_calls': 4, 'teams': 28, 'n': 8}
{'matches': 18, 'n_calls': 1, 'teams': 36, 'n': 9}
{'matches': 23, 'n_calls': 1, 'teams': 45, 'n': 10}
{'matches': 28, 'n_calls': 1, 'teams': 55, 'n': 11}
{'matches': 33, 'n_calls': 1, 'teams': 66, 'n': 12}
...
{'matches': 2186, 'n_calls': 1, 'teams': 4371, 'n': 94}
{'matches': 2233, 'n_calls': 1, 'teams': 4465, 'n': 95}
{'matches': 2280, 'n_calls': 1, 'teams': 4560, 'n': 96}
{'matches': 2328, 'n_calls': 1, 'teams': 4656, 'n': 97}
{'matches': 2377, 'n_calls': 1, 'teams': 4753, 'n': 98}
{'matches': 2426, 'n_calls': 1, 'teams': 4851, 'n': 99}
{'matches': 2475, 'n_calls': 1, 'teams': 4950, 'n': 100}

Ответ 2

Я не знаю Python, но я не мог удержаться от этого в Ruby. Надеюсь, это будет легко переведено на Python. Если вы не знаете Ruby, я буду рад объяснить, что происходит здесь:

num_players = gets.to_i
players = (1..num_players).to_a
teams = players.combination(2).to_a

def shuffle_teams( teams, players )
  shuffled_teams = teams.shuffle
  x = 0
  while x < shuffled_teams.length
    if shuffled_teams[x] - shuffled_teams[x + 1] == shuffled_teams[x]
      x += 2
    else
      return shuffle_teams( teams, players )
    end
  end
  x = 0
  while x < shuffled_teams.length
    team_1 = shuffled_teams[x]
    team_2 = shuffled_teams[x + 1]
    waiting = players.select do |player|
      ![team_1, team_2].flatten.include?(player)
    end
    print "(#{team_1}, #{team_2}), waiting: #{waiting}\n"
    x += 2
  end
end

shuffle_teams( teams, players )

Это дает правильный результат для 4 игроков:

([3, 4], [1, 2]), waiting: []
([1, 3], [2, 4]), waiting: []
([2, 3], [1, 4]), waiting: []

и для 5 игроков:

([2, 4], [1, 3]), waiting: [5]
([1, 5], [3, 4]), waiting: [2]
([1, 4], [2, 5]), waiting: [3]
([3, 5], [1, 2]), waiting: [4]
([2, 3], [4, 5]), waiting: [1]

Однако он не работает для 6 или 7 игроков, потому что каждый из них приводит к нечетному количеству комбинаций. Как эта проблема решена в реальной жизни? Так или иначе, одной команде придется играть дважды.

Изменить: Этот script теперь будет обрабатывать 6 или 7 пулов игроков, дублируя одну из команд. Его легко реплицировать в Python, поскольку он просто полагается на перетасовку массива команд, пока они не согласятся в соответствующем порядке. Сначала мне показалось, что я немного обманывал этот подход, но, учитывая анонимное объяснение, что это NP-полная проблема (предполагая, что я правильно понимаю, что это означает:-), это может быть лучший способ решить проблему для небольшие бассейны (взорвать пулы размером более 9 или около того, в зависимости от вашей системы, но, к счастью, это выходит за рамки нашего сценария). Плюс случайный порядок имеет то преимущество, что он безличный, что может пригодиться, если игроки расстраиваются из-за необходимости играть дважды, не будучи забитым во второй раз! Здесь script:

num_players = gets.to_i
players = (1..num_players).to_a
teams = players.combination(2).to_a

def shuffle_teams( teams, players )
  shuffled_teams = teams.shuffle
  x = 0
  while x < shuffled_teams.length
    if !shuffled_teams[x + 1]
      shuffled_teams[x + 1] = shuffled_teams.find do |team|
        shuffled_teams[x] - team == shuffled_teams[x]
      end
    end
    if shuffled_teams[x] - shuffled_teams[x + 1] == shuffled_teams[x]
      x += 2
    else
      return shuffle_teams( teams, players )
    end   
  end
  x = 0
  while x < shuffled_teams.length
    team_1 = shuffled_teams[x]
    team_2 = shuffled_teams[x + 1]
    waiting = players.select do |player|
      ![team_1, team_2].flatten.include?(player)
    end
    print "(#{team_1}, #{team_2}), waiting: #{waiting}\n"
    x += 2
  end
end

shuffle_teams( teams, players )

А вот вывод, со временем:

4
([1, 4], [2, 3]), waiting: []
([1, 2], [3, 4]), waiting: []
([2, 4], [1, 3]), waiting: []

real    0m0.293s
user    0m0.035s
sys 0m0.015s

5
([4, 5], [1, 2]), waiting: [3]
([1, 4], [2, 3]), waiting: [5]
([2, 5], [1, 3]), waiting: [4]
([2, 4], [3, 5]), waiting: [1]
([3, 4], [1, 5]), waiting: [2]

real    0m0.346s
user    0m0.040s
sys 0m0.010s

6
([3, 4], [1, 2]), waiting: [5, 6]
([3, 5], [2, 4]), waiting: [1, 6]
([3, 6], [1, 5]), waiting: [2, 4]
([1, 6], [2, 5]), waiting: [3, 4]
([2, 3], [4, 6]), waiting: [1, 5]
([2, 6], [4, 5]), waiting: [1, 3]
([5, 6], [1, 4]), waiting: [2, 3]
([1, 3], [2, 4]), waiting: [5, 6]

real    0m0.348s
user    0m0.035s
sys 0m0.020s

7
([1, 6], [4, 5]), waiting: [2, 3, 7]
([2, 6], [1, 4]), waiting: [3, 5, 7]
([2, 7], [1, 3]), waiting: [4, 5, 6]
([3, 4], [2, 5]), waiting: [1, 6, 7]
([3, 5], [2, 4]), waiting: [1, 6, 7]
([1, 7], [5, 6]), waiting: [2, 3, 4]
([6, 7], [1, 5]), waiting: [2, 3, 4]
([3, 6], [4, 7]), waiting: [1, 2, 5]
([1, 2], [5, 7]), waiting: [3, 4, 6]
([3, 7], [4, 6]), waiting: [1, 2, 5]
([2, 3], [1, 6]), waiting: [4, 5, 7]

real    0m0.332s
user    0m0.050s
sys 0m0.010s

Ответ 3

Вы можете выразить это как проблему покрытия набора. С 4 игроками возьмите набор всех (неупорядоченных) пар игроков:

PP := {{0,1}, {0,2}, {0,3}, {1,2}, {1,3}, {2,3}}

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

M := {{{0,1},{2,3}}, {{0,2},{1,3}}, {{0,3},{1,2}}}

Ваша проблема в том, что вы хотите найти наименьшее подмножество этого множества, чтобы его объединение было множеством всех пар игроков, PP.

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

Поскольку вы ограничиваетесь небольшими наборами, вполне разумно просто решить его грубой силой.

Мы знаем, что это займет не менее ceil(N * (N-1) / 4) совпадений (так как там N * (N-1) / 2 разные пары, и каждое совпадение может содержать не более 2 новых пар). Это дает нам алгоритм.

import itertools

def mincover(n):
    pairs = set(map(tuple, itertools.combinations(range(n), 2)))
    matches = itertools.combinations(pairs, 2)
    matches = [m for m in matches if not(set(m[0]) & set(m[1]))]
    for subset_size in xrange((len(pairs) + 1) // 2, len(pairs) + 1):
        for subset in itertools.combinations(matches, subset_size):
            cover = set()
            for s in subset: cover |= set(s)
            if cover == pairs:
                return subset

for i in xrange(4, 8):
    print i, mincover(i)

Это довольно медленно, особенно для 6 и 7 игроков. Это может быть немного улучшено с помощью ручного кодированного поиска, который не учитывает совпадения, которые не добавляют новые пары игроков, а также используют симметрию и всегда включают {{0,1}, {2,3}}.

Ответ 4

Там должен быть лучший способ сделать это, но вот начало:

import itertools
import operator
from copy import deepcopy as clone

def getPossibleOpponents(numPlayers):
    matches = list(itertools.combinations(itertools.combinations(range(1,numPlayers+1), 2), 2))
    possibleMatches = [match for match in matches if len(set(itertools.chain.from_iterable(match)))==4]
    answer, playedTeams = {}, set()
    opponents = {}
    for team, teams in itertools.groupby(possibleMatches, key=operator.itemgetter(0)):
        playedTeams.add(team)
        opponents[team] = [t for t in next(teams) if t!=team]

    return opponents

def updateOpponents(opponents, playedTeams):
    for team in playedTeams:
        if team in opponents:
            opponents.pop(team)
    for k,v in opponents.items():
        opponents[k] = [team for team in v if team not in playedTeams]

def teamSeatings(opponents, answer=None):
    if answer is None:
        answer = {}
    if not len(opponents):
        if not(len(answer)):
            return None
        print(answer)
            sys.exit(0)

    for k,v in opponents.items():
        if not v:
            return None

        newOpponents = clone(opponents)
        for away in opponents[k]:
            if k in newOpponents:
                newOpponents.pop(k)
            answer[k] = away
            updateOpponents(newOpponents, {itertools.chain.from_iterable(i[0] for i in answer.items())})
            teamSeatings(newOpponents, answer)

if __name__ == "__main__":
    opps = getPossibleOpponents(5)
    teamSeatings(opps)

Ответ 5

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

Whist Round Robin

Проблема планирования турнира с парами, состоящими из двух человек, стоящих перед другой командой из двух человек, называется Whist Round Robin - Подробнее и найти алгоритмы здесь.

Проще всего реализовать в случае с 4n количеством игроков. Другие три случая построены с использованием призрачных игроков и команды призраков. Игроки, которые должны встретиться с командой призраков, просто сидят в этом раунде.

Основная идея заключается в том, что один игрок заблокирован, позволяет говорить один игрок. Другие игроки затем "вращаются", так что игрок 2 объединяется с игроком 1 в первом раунде и встречает игроков 2 и 3. Следующий раунд игрока 1 остается и объединяется с игроком 3, и они сталкиваются с игроками 2 и 4. Смотрите эту визуализацию, чтобы Я позаимствовал из ссылки выше.

Я реализовал алгоритмы, описанные там, чтобы запланировать foosball torunament со схожими характеристиками, такими как мяч для пляжного волейбола, и он работал как шарм.

У вас не должно возникнуть проблемы с отображением этого в python. Если вы это сделаете - вернитесь с определенным вопросом. Удачи!:)

Ответ 6

Хорошая модель для вашей проблемы - это полный неориентированный граф:

Вершины представляют игроков.
Края представляют собой команду из двух игроков.

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

Так как число ребер в полном графе n вершин равно (n * (n - 1)) / 2, то очевидно, что в случае, когда это число является нечетным, одно ребро должно использоваться дважды.

Ответ 7

Извините, что продолжаю публиковать в Ruby, но я думаю, что я просто взломал его, и мне нужно поделиться. Надеюсь, вся моя напряженная работа поможет вам реализовать ее в Python:).

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

num_players = gets.to_i
players = (1..num_players).to_a
teams = players.combination(2).to_a
first_half = Float(teams.length / 2.0).ceil
first_half_teams = teams[0..(first_half - 1)]
second_half_teams = teams[first_half..-1]
possible_lineups = []
matches = []
matched = []

first_half_teams.each do |team|
  opponents = second_half_teams.select do |team_2|
    team - team_2 == team
  end
  possible_lineups << [team, opponents]
end

possible_lineups.each do |lineup|
  team_1 = lineup[0]
  team_2 = lineup[1].find do |team|
    !matched.include?(team)
  end
  if !team_2
    thief_team = possible_lineups.find do |test_team|
      test_team[1] - lineup[1] != test_team[1] &&
      test_team[1].find{ |opponent| !matched.include?(opponent) }
    end
    if thief_team
      new_opponent = thief_team[1].find{ |opponent| !matched.include?(opponent) }
      matched << new_opponent
      old_lineup = matches.find do |match|
        match[0] == thief_team[0]
      end
      team_2 = old_lineup[1]
      matches.find{ |match| match[0] == thief_team[0]}[1] = new_opponent
    else
      team_2 = second_half_teams.find do |team|
        lineup[0] - team == lineup[0]
      end
    end
  end
  matches << [team_1, team_2]
  matched << team_2
end

matches.each do |match|
  left_out = players.select{ |player| !match.flatten.include?(player) }
  print match, ", waiting: ", left_out, "\n"
end

print "greater: ", matches.flatten(1).find{ |team| matches.flatten(1).count(team) > teams.count(team) }, "\n"
print "less: ", matches.flatten(1).find{ |team| matches.flatten(1).count(team) < teams.count(team) }, "\n"

Как проверка реальности, у меня есть script сравнить последний массив совпадений с исходным массивом уникальных комбинаций пары игроков. В случаях, когда количество комбинаций пары игроков равно (например, размер пула = 4 или 5), не должно быть пар, которые появляются в финальном матчевом массиве большее или меньшее количество раз, чем они появляются в исходном массиве комбинаций ( т.е. каждая пара должна отображаться ровно один раз в каждом массиве). В случаях, когда количество комбинаций нечетное (n = 6 или 7), должна быть ровно одна пара, которая появляется еще раз в массиве совпадений, чем в массиве комбинаций. Там никогда не должно быть пары, которая появляется меньше в массиве совпадений, чем в массиве комбинаций. Здесь вывод:

4
[[1, 2], [3, 4]], waiting: []
[[1, 3], [2, 4]], waiting: []
[[1, 4], [2, 3]], waiting: []
greater: 
less: 

5
[[1, 2], [3, 5]], waiting: [4]
[[1, 3], [2, 4]], waiting: [5]
[[1, 4], [2, 5]], waiting: [3]
[[1, 5], [3, 4]], waiting: [2]
[[2, 3], [4, 5]], waiting: [1]
greater: 
less: 

6
[[1, 2], [3, 4]], waiting: [5, 6]
[[1, 3], [2, 6]], waiting: [4, 5]
[[1, 4], [3, 5]], waiting: [2, 6]
[[1, 5], [3, 6]], waiting: [2, 4]
[[1, 6], [4, 5]], waiting: [2, 3]
[[2, 3], [4, 6]], waiting: [1, 5]
[[2, 4], [5, 6]], waiting: [1, 3]
[[2, 5], [3, 4]], waiting: [1, 6]
greater: [3, 4]
less: 

7
[[1, 2], [3, 4]], waiting: [5, 6, 7]
[[1, 3], [4, 5]], waiting: [2, 6, 7]
[[1, 4], [3, 5]], waiting: [2, 6, 7]
[[1, 5], [3, 6]], waiting: [2, 4, 7]
[[1, 6], [3, 7]], waiting: [2, 4, 5]
[[1, 7], [4, 6]], waiting: [2, 3, 5]
[[2, 3], [4, 7]], waiting: [1, 5, 6]
[[2, 4], [5, 6]], waiting: [1, 3, 7]
[[2, 5], [6, 7]], waiting: [1, 3, 4]
[[2, 6], [5, 7]], waiting: [1, 3, 4]
[[2, 7], [3, 4]], waiting: [1, 5, 6]
greater: [3, 4]
less:

Примечание для FMc: Ваши комментарии помогли мне улучшить мое мышление по этой проблеме. Алгоритм "мозг-мертвый" приближает вас, но не совсем к решению. Когда n > 4, всегда существует одна пара игроков, оставшихся без противоположной пары, когда вы используете чисто жадный алгоритм. Мой алгоритм имеет дело с этим, возвращаясь и принимая подходящую противоположную пару из уже согласованной команды, если и только если последняя команда может использовать другую противоположную пару, которая еще не была использована. Кажется, это единственное исправление (помимо настройки для нечетных чисел комбинаций), и, насколько я могу судить, это нужно сделать только один раз.