Создание скошенного кронштейна для турнира

Question

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

Если бы мы имели 8 команд это приведет:

раунда 1 =========> Раунд 2 =========> Раунд 3
команды 1 против команды 8
Команда 4 против команды 5 ==> Команда 1 против команды 4 ==> Команда 1 Команда 2 против
команды 3 против Team 6 ==> Team 3 против команды 2
Команда 2 Команда против 7

Обращаем внимание на заказ t в первом раунде, поскольку мой вопрос будет развиваться вокруг правильного порядка команд. Вы увидите, что команда 1 находится на вершине, а команда 2 - внизу.

Теперь я понял простую функцию, которая будет пара команд в 1-м раунде, чтобы произвести правильные матчей:

//Bracket Structure represents the order of teams in which they should be printed in round 1 for specific number of teams. 
//As you see I have to manually specify for each team size, I wish to write an algorithm that will calculate this for me so that I do not have a maximum teams restriction. 
private static readonly Dictionary<int, int[]> BracketStructure = new Dictionary<int, int[]> 
{ 
    //2 is number of teams, 0 represents the team in the array, so 0 is actually team 1, 1 is team 2, etc... 
    { 2, new [] { 0 } }, 
    { 4, new [] { 0, 1} }, 
    { 8, new [] { 0, 3, 2, 1} }, 
    { 16, new [] { 0, 7, 4, 3, 2, 5, 6, 1} }, 
    { 32, new [] { 0, 15, 7, 8, 3, 12, 4, 11, 1, 14, 6, 9, 2, 13, 5, 10 }}, 
    { 64, new [] { 0, 31, 16, 15, 8, 23, 24, 7, 3, 28, 19, 12, 11, 20, 27, 4, 1, 30, 17, 14, 9, 22, 25, 6, 2, 29, 18, 13, 10, 21, 26, 5 }} 
}; 

private static void CreateMatchups(int totalTeams) 
{ 
    var teams = new List<int>(); 
    var matchups = new List<string>(); 
    var c = 1; 
    while (totalTeams >= c) 
    { 
     teams.Add(c); 
     c++; 
    } 

    for (var i = 0; i < teams.Count/2; i++) 
    { 
     matchups.Add(teams[i] + " vs " + teams[totalTeams - (i + 1)]); 
    } 
    PrintBracket(matchups, BracketStructure[totalTeams]); 
} 

private static void PrintBracket(IReadOnlyList<string> matchups, IEnumerable<int> teams) 
{ 
    foreach (var team in teams) 
    { 
     Console.WriteLine(matchups[team]); 
    } 
} 

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

команды 1 против команды 8
команда 2 Team против 7
команды 3 против команды 6
Команда 4 против Команда 5

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

Я основывали свою упорядоченность на http://www.printyourbrackets.com/

я это первоначально на https://softwareengineering.stackexchange.com/, но мне сказали, переполнение стека является правильным местом для этого вопроса, так что я отправляю его здесь вместо этого.

Для получения дополнительной информации о том, что затравки кронштейн, вы можете прочитать здесь: https://en.wikipedia.org/wiki/Seed_(sports)

EDIT:

Я наткнулся на это, как я делал больше исследований: https://jsfiddle.net/vrnb16r9/1/

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

Раунд 1 =========> Круглый 2 =========> Круглый 3
команды 1 против команды 8
Команда 4 против команды 5 ==> Team 1 против команды 4 ==> Команда 1 Команда 2 против
команды 3 против Team 6 ==> Команда 3 против команды 2
команды 2 против команды 7

Однако его формула печатает ее, как это:

Круглый 1 =========> Круглые 2 =========> Круглые 3
команды 1 против команды 8
Команда 4 против команды 5 ==> Team 1 против команда 4 ==> команда 1 команда 2 против
команды 2 против команды 7 ==> Team 2 против команды 3
команды 3 против команды 8

Обратите внимание, что команда 2 вывозится раз и команда 3 снизилась один раз? Хотя его формула по-прежнему приводит к правильным спариваниям в каждом раунде, у него нет 100% правильного порядка. Я понимаю, что он просто поменял позицию двух команд, и это в конечном счете не имеет значения, потому что, несмотря ни на что, в следующем раунде будут правильные совпадения. Однако мне все равно хотелось бы выяснить, как их получить в точном порядке, который они предполагают , так же, как и на печатной ссылке, которую я дал выше. Я считаю, что его подход находится в правильном направлении, выясняет победителя и прокладывает себе путь назад, однако мне трудно понять его код.

EDIT 2:

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

Answer 1

Я издам код, который, как я думаю, делает то, что вы хотите, но заказ не является точным, как вы пожелаете.Я думаю, что эти таблицы на printyourbracket.com были созданы вручную, а не по алгоритму (я также посмотрел 16 и 32 версии). В общем, вот код. Сначала определим маленькие классы, чтобы сделать его легче читать код:

class Round { 
    public Match[] Matches { get; set; } 
} 

class Match { 
    // where number is player's seed number   
    public int PlayerA { get; set; } 
    public int PlayerB { get; set; } 
} 

А вот алгоритм:

static Round[] Generate(int playersNumber) {   
     // only works for power of 2 number of players 
     var roundsNumber = (int) Math.Log(playersNumber, 2); 
     var rounds = new Round[roundsNumber]; 
     for (int i = 0; i < roundsNumber; i++) { 
      var round = new Round(); 
      var prevRound = i > 0 ? rounds[i - 1] : null; 
      if (prevRound == null) { 
       // if first round - result is known 
       round.Matches = new[] { 
        new Match() { 
         PlayerA = 1, 
         PlayerB = 2 
        } 
       }; 
      } 
      else { 
       round.Matches = new Match[prevRound.Matches.Length*2]; 
       // find median. For round 2 there are 4 players and median is 2.5 (between 2 and 3) 
       // for round 3 there are 8 players and median is 4.5 (between 4 and 5) 
       var median = (round.Matches.Length*2 + 1)/2f; 
       var next = 0; 
       foreach (var match in prevRound.Matches) { 
        // you can play here by switching PlayerA and PlayerB or reordering stuff 
        round.Matches[next] = new Match() { 
         PlayerA = match.PlayerA, 
         PlayerB = (int) (median + Math.Abs(match.PlayerA - median)) 
        }; 
        next++; 
        round.Matches[next] = new Match() { 
         PlayerA = match.PlayerB, 
         PlayerB = (int) (median + Math.Abs(match.PlayerB - median)) 
        }; 
        next++; 
       } 
      } 
      rounds[i] = round; 
     } 
     return rounds.Reverse().ToArray(); 
    } 

Использование:

var rounds = Generate(8); 
foreach (var round in rounds) { 
    foreach (var match in round.Matches) { 
     Console.WriteLine("{0} vs {1}", match.PlayerA, match.PlayerB); 
    } 
    Console.WriteLine(); 
} 
Console.ReadKey(); 

В основном мы начинаем в корне (1,2) и идти в обратном направлении, сопоставляя игроков высокого ранга с самыми низкими рангами, вторым самым высоким до второго минимума и так далее. Из вашего описания это похоже на алгоритм javascript, хотя и не смотрел на их реализацию. Вы можете играть с этим кодом, чтобы попытаться добиться желаемого заказа, но если эта таблица была сделана людьми - это может быть невозможно.

Answer 2

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

(Рабочий пример на: https://dotnetfiddle.net/Z1CJib)

public class Team 
{ 
    public Team(string name, int seed){ 
     Name = name; 
     Seed = seed; 
    } 

    public string Name {get; set;} 

    public int Seed {get; set;} 

    //simple method to compare two teams' seed values and return the better (1 > 2) team 
    public static Team GetBetterSeed(Team t1, Team t2){ 
     return t1.Seed < t2.Seed ? t1 : t2; 
    } 
} 

public class Matchup 
{ 
    public Matchup(Team t1, Team t2){ 
     Team1 = t1; 
     Team2 = t2; 
    } 

    public Team Team1 {get; set;} 
    public Team Team2 {get; set;} 

    //"Team 1's Name vs. Team 2's Name" 
    public override string ToString(){ 
     return Team1.Name + " vs. " + Team2.Name; 
    } 

    //using the GetBetterSeed() method above we can get which team out of a matchup is favored 
    public Team GetFavored(){ 
     return Team.GetBetterSeed(Team1, Team2); 
    } 
} 

Теперь вы можете создать набор Team с, которые будут иметь имена и семена значения

var newTeam = new Team("Team Name", 1); 
teamList.Add(newTeam); 

или же вы хотите создать список команды.

---

Ваш алгоритм матч на самом деле работает (так долго ваш счетчик команда даже), я просто отделяется создание команды из матчей:

private static List<Matchup> CreateMatchups(List<Team> teams) 
{ 
    var matchups = new List<Matchup>(); 

    for (int i = 0; i < teams.Count/2; i++) 
    { 
     matchups.Add(new Matchup(teams[i], teams[teams.Count - (i+1)])); 
    } 

    return matchups; 
} 

Чтобы напечатать матчей, чтобы вы можете использовать Linq's OrderBy. Вы даете OrderBy функцию, говоря ему, что часть элемента, который вы хотите приказать (в данном случае Team.Seed) и это даст набор, чтобы вы заказывали наименьшего к наибольшему по этому значению:

private static void PrintBracket(List<Matchup> Matchups) 
{ 
    foreach(var matchup in Matchups.OrderBy(x=> x.GetFavored().Seed)){ 
     Console.WriteLine(matchup); 
    } 
} 

Answer 3

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

(скрипка https://dotnetfiddle.net/nD8dXb)

Рекурсивные функции:

public static void branch(int seed, int level, int limit) { 
    var levelSum = (int) Math.Pow(2, level) + 1; 

    if (limit == level + 1) { 
     Console.WriteLine("Seed {0} vs. Seed {1}", seed, levelSum - seed); 
     return; 
    } 
    else if (seed % 2 == 1) { 
     branch(seed, level + 1, limit); 
     branch(levelSum - seed, level + 1, limit); 
    } 
    else { 
     branch(levelSum - seed, level + 1, limit); 
     branch(seed, level + 1, limit); 
    } 
} 

Назовите это для каждого раунда:

var numberTeams = 16; // must be a power of 2 
var limit = (int) (Math.Log(numberTeams, 2) + 1); 

for (int round = 1; round < limit; round++) { 
    Console.WriteLine("Round #{0}", round); 
    branch(1, 1, limit - round + 1); 
    Console.WriteLine(); 
} 

Выход:

Round #1 
Seed 1 vs. Seed 16 
Seed 8 vs. Seed 9 
Seed 5 vs. Seed 12 
Seed 4 vs. Seed 13 
Seed 3 vs. Seed 14 
Seed 6 vs. Seed 11 
Seed 7 vs. Seed 10 
Seed 2 vs. Seed 15 

Round #2 
Seed 1 vs. Seed 8 
Seed 4 vs. Seed 5 
Seed 3 vs. Seed 6 
Seed 2 vs. Seed 7 

Round #3 
Seed 1 vs. Seed 4 
Seed 2 vs. Seed 3 

Round #4 
Seed 1 vs. Seed 2