Как создать расписание турниров в Ruby?

Question

Я искал повсюду, в том числе в архивах Stack Overflow, ответ на вопрос, как это сделать, я пытался свернуть свой собственный, но потерпел неудачу, поэтому решил разместить свой запрос здесь.

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

Введите:

('A'..'H').to_a

Выход:

[[['A','H'], ['B','G'], ['C','F'], ['D','E']],
 [['A','G'], ['B','F'], ['C','E'], ['D','H']],
 [['A','F'], ['B','E'], ['C','D'], ['G','H']],
 [['A','E'], ['B','D'], ['C','H'], ['F','G']],
 [['A','D'], ['B','C'], ['E','G'], ['F','H']],
 [['A','C'], ['B','H'], ['D','G'], ['E','F']],
 [['A','B'], ['C','G'], ['D','F'], ['E','H']]]

Есть идеи?

Вот что я сделал до сих пор. Он немного грязный и не возвращается в нужном мне порядке.

items = ('A'..'H').to_a
combinations = []

1.upto(7) do |index|
  curitems = items.dup
  combination = []
  1.upto(items.size / 2) do |i|
    team1 = curitems.delete_at(0)
    team2 = curitems.delete_at(curitems.size - index) || curitems.delete_at(curitems.size - 1)
    combination << [team1, team2]
  end
  combinations << combination
end

pp combinations

Вывод закрыт, но не в правильном порядке:

[[["A", "H"], ["B", "G"], ["C", "F"], ["D", "E"]],
 [["A", "G"], ["B", "F"], ["C", "E"], ["D", "H"]],
 [["A", "F"], ["B", "E"], ["C", "D"], ["G", "H"]],
 [["A", "E"], ["B", "D"], ["C", "H"], ["F", "G"]],
 [["A", "D"], ["B", "C"], ["E", "G"], ["F", "H"]],
 [["A", "C"], ["B", "H"], ["D", "E"], ["F", "G"]],
 [["A", "B"], ["C", "G"], ["D", "H"], ["E", "F"]]]

Вы заметите, что мой код дает мне две комбинации D <-> H (последняя строка и вторая строка), и это не сработает.

Мое понимание требований ОП [FM]:

• Дано N команд (например, 8 команды: A..H).
• Создать расписание турниров, состоящий из R раундов игры (7 в нашем примере) и G игр (28 в наш пример).
• Где каждая команда играет одну команду ровно один раз.
• Где каждая команда играет один раз в каждом раунде.
• И (трудная часть), где заказ игр в течение раунда работает так:
• Команда высшего ранга (A) играет команда с низким рейтингом (H) первая.
• Если кандидатский матч отклонен за нарушение правила повторения команда с низким рейтингом на «задний план» и образуют другие Первый матч. Тогда сопоставим отсталые команды, использующие тот же правила. (Например: во втором раунде Первый кандидат на матч A-H отклонено как повтор, поэтому игра 1 будет быть A-G, а H будет сидеть на спине горелка, в паре с D в качестве последняя игра в раунде).
• При добавлении команд на задний план, добавить их в начало этого списка (т.е. сохранить порядок ранга на задний ход).
• Примечание : Раунд 5 - хитрый. Первые 2 игры просты. Третья игра тогда будет E-H; однако это создает сценарий где 4-я игра будет повторением (F-G). Так что алгоритм должен вернуться назад, отклонить спаривание E-H и вместо этого перейдите на E-G в 3-м игры.

Answer 1

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

games = (1...teams.size).map do |r|
  t = teams.dup
  (0...(teams.size/2)).map do |_|
    [t.shift,t.delete_at(-(r % t.size + (r >= t.size * 2 ? 1 : 0)))]
  end
end

Answer 2

Вы, кажется, хотите, чтобы круговой график. Принцип прост:

Если вы начинаете с этой настройкой (команды в верхнем ряду играют против соответствующей нижней команды):

A B C D
H G F E

Вы устанавливаете одну команду как фиксированную (например, A), а остальные поворачиваете (например, по часовой стрелке):

A H B C     A G H B     A F G H     A E F G    A D E F    A C D E  
G F E D     F E D C     E D C B     D C B H    C B H G    B H G F

Вуаля, 7 раундов, и каждая команда играет друг с другом.

Редактировать: я изменил порядок перечисления в этом примере, чтобы отразить ваш пример вывода, но это дает право только противникам A.

Answer 3

Я прошу прощения за Python-ность этого кода. Если повезет, кто-то переведет.

def tourney(teams):
    N = len(teams)
    R = N-1 # rounds
    M = N/2 # matches per round
    sched = [[None] * M for i in range(R)]
    played = set()

    def fill(i, t):
        # Replenish t at the start of each round.
        if i % M == 0:
            t = teams[:]

        # Pick out the highest-seeded team left in t.
        topseed = t.pop(min(range(len(t)), key=lambda i: teams.index(t[i])))

        # Try opponents in reverse order until we find a schedule that works.
        for j, opp in reversed(list(enumerate(t))):
            match = topseed, opp
            if match not in played:
                # OK, this is match we haven't played yet. Schedule it.
                sched[i // M][i % M] = match
                played.add(match)

                # Recurse, if there are any more matches to schedule.
                if i + 1 == R * M or fill(i + 1, t[j+1:]+t[:j]):
                    return True  # Success!

                # If we get here, we're backtracking. Unschedule this match.
                played.remove(match)
        return False

    if not fill(0, []):
        raise ValueError("no schedule exists")
    return sched

Answer 4

Я создал драгоценный камень, round_robin_tournament , который может оказаться полезным.

Просто беги

students = %w(John Paul Ringo George)
teams = RoundRobinTournament.schedule(students)

И teams будет массивом каждого дня, каждый день - массивом пар.

Answer 5

Вот реализация в ruby ​​1.8.6 в соответствии со спецификацией FM, дающая правильный вывод для 8 команд (Большое спасибо FM за отличную работу!):

#!/usr/bin/env ruby

require 'pp'
require 'enumerator'

class Array
  # special round robin scheduling
  def schedule
    res, scheduled = [], []
    (length-1).times { dup.distribute(scheduled, []) }
    # convert list of games to list of rounds
    scheduled.each_slice(length/2) {|x| res.push x}
    aux = res.inject {|a, b| a+b}
    raise if aux.uniq.length != aux.length
    res
  end
  # pair the teams in self and backburner and add games to scheduled
  def distribute(scheduled, backburner)
    # we are done if list is empty and back burners can be scheduled
    return true if empty? && backburner.empty?
    return backburner.distribute(scheduled, []) if empty?
    # take best team and remember if back burner list offered alternatives
    best, alternatives = shift, !backburner.empty?
    # try each team starting from the last
    while other = pop do
      # add team to the back burner list if best played it already
      if scheduled.include? [best, other]
        backburner.unshift(other)
        next
      end
      # schedule the game
      scheduled.push [best, other]
      # try if rest can be scheduled
      return true if dup.distribute(scheduled, backburner.dup)
      # if not unschedule game and add other to back burner list
      scheduled.pop
      backburner.unshift(other)
    end
    # no possible opponent was found, so try alternatives from back burners list
    return alternatives && backburner.unshift(best).distribute(scheduled, [])
  end
end

pp %w{ A B C D E F G H }.schedule

__END__

Output:
[[["A", "H"], ["B", "G"], ["C", "F"], ["D", "E"]],
 [["A", "G"], ["B", "F"], ["C", "E"], ["D", "H"]],
 [["A", "F"], ["B", "E"], ["C", "D"], ["G", "H"]],
 [["A", "E"], ["B", "D"], ["C", "H"], ["F", "G"]],
 [["A", "D"], ["B", "C"], ["E", "G"], ["F", "H"]],
 [["A", "C"], ["B", "H"], ["D", "G"], ["E", "F"]],
 [["A", "B"], ["C", "G"], ["D", "F"], ["E", "H"]]]

Answer 6

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

Answer 7

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

require 'pp'

def tournament (teams)
    teams.reverse!

    # Hash of hashes to keep track of matchups already used.
    played = Hash[ * teams.map { |t| [t, {}] }.flatten ]

    # Initially generate the tournament as a list of games.
    games = []
    return [] unless set_game(0, games, played, teams, nil)

    # Convert the list into tournament rounds.
    rounds = []
    rounds.push games.slice!(0, teams.size / 2) while games.size > 0
    rounds
end

def set_game (i, games, played, teams, rem)
    # Convenience vars: N of teams and total N of games.
    nt  = teams.size
    ng  = (nt - 1) * nt / 2

    # If we are working on the first game of a round,
    # reset rem (the teams remaining to be scheduled in
    # the round) to the full list of teams.
    rem = Array.new(teams) if i % (nt / 2) == 0

    # Remove the top-seeded team from rem.
    top = rem.sort_by { |tt| teams.index(tt) }.pop
    rem.delete(top)

    # Find the opponent for the top-seeded team.
    rem.each_with_index do |opp, j|
        # If top and opp haven't already been paired, schedule the matchup.
        next if played[top][opp]
        games[i] = [ top, opp ]
        played[top][opp] = true

        # Create a new list of remaining teams, removing opp
        # and putting rejected opponents at the end of the list.
        rem_new = [ rem[j + 1 .. rem.size - 1], rem[0, j] ].compact.flatten

        # Method has succeeded if we have scheduled the last game
        # or if all subsequent calls succeed.
        return true if i + 1 == ng
        return true if set_game(i + 1, games, played, teams, rem_new)

        # The matchup leads down a bad path. Unschedule the game
        # and proceed to the next opponent.
        played[top][opp] = false
    end

    return false
end

pp tournament(ARGV)

Answer 8

Как насчет

[*'A'..'H'].permutation(2).to_a
 => [["A", "B"], ["A", "C"], ["A", "D"], ["A", "E"], ["A", "F"], ["A", "G"], ["A", "H"], ["B", "A"], ["B", "C"], ["B", "D"], ["B", "E"], ["B", "F"], ["B", "G"],....

Редактировать: Просто заметил, что вывод не в желаемом формате, но, возможно, это все еще полезно для кого-то еще.

Answer 9

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

def round_robin(teams)
  raise "Only works for even number of teams" unless teams.length.even?
  first = teams.shift                               # Put one team in the middle, not part of the n-gon
  size  = teams.length                              # The size of the n-gon without one team
  pairs = (1..(size/2)).map{ |i| [i,size-i].sort }  # The 'lines' that connect vertices in the n-gon
  (0...size).map{                                   
    teams.unshift( teams.pop )                      # Rotate the n-gon
    # Combine the special case with the vertices joined by the lines
    [ [ first, teams[0] ], *pairs.map{ |a,b| [ teams[a], teams[b] ] } ]
  }
end

teams    = ('A'..'H').to_a
schedule = round_robin(teams)
puts schedule.map{ |round| round.map{ |teams| teams.join }.join(' ') }
#=> AH BG CF DE
#=> AG HF BE CD
#=> AF GE HD BC
#=> AE FD GC HB
#=> AD EC FB GH
#=> AC DB EH FG
#=> AB CH DG EF

Answer 10

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

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

при условии, что команды являются здесь модельным объектом, а num_teams - это количество команд

  @tms = teams.all    
  matchups_play_each_team_once = (0...num_teams-1).map do |r|
    t = @tms.dup
    first_team = t.shift
    r.times do |i|
      t << t.shift
    end
    t = t.unshift(first_team)  
    tms_away = t[0...num_teams/2]
    tms_home = t[num_teams/2...num_teams].reverse
    (0...(num_teams/2)).map do |i|
      [tms_away[i],tms_home[i]]
    end
  end