algoritmo Round Robin Tournament em C #

StackOverflow https://stackoverflow.com/questions/1293058

  •  18-09-2019
  •  | 
  •  

Pergunta

Eu estou tendo alguns problemas para alcançar este pequeno round robin projeto. O que eu tento fazer é gerar um calendário pré-visualização de jogos

então eu quero saída;

Dia 1: Equipa 1 vs Team 2; Equipe 3 vs Equipe 4; Equipe 5vs Equipe 6;

dia 2 Equipa 1 vs Equipe 4; Time 6 vs 3; Equipe 2 vs Equipe 5;

até o final do campeonato;

Aqui está o código que eu tenho até agora, mas eu estou tendo problemas para deixar o primeiro time fixo, enquanto o resto dos gira matriz ...: 

static void Main(string[] args)
   {
        string[] ListTeam = new string[] {"Equipe1", "Equipe2", "Equipe3", "Equipe4", "Equipe5", "Equipe6"};
        IList<Match> ListMatch = new List<Match>();
        it NumberOfDays = (ListTeam.Count()-1);
        int y = 2;

        for (int i = 1; i <= NumberOfDays; i++)
        {
            Console.WriteLine("\nDay {0} : \n",i);
            Console.WriteLine(ListTeam[0].ToString() + " VS " + ListTeam[i].ToString());

            for (y =ListTeam.Count(); y>0 ; y--)
            {
                Console.WriteLine(ListTeam[y].ToString() + " VS " + ListTeam[y+1].ToString());
                y++;
            }

        }
    }

EDIT: Eu encontrei um exemplo de código em java, mas eu não posso traduzi-lo ...

Foi útil?

Solução

Isso deve ser fácil o suficiente para fazer usando a aritmética modular:

UPDATE 2: (Como prometido algoritmo correto) 

public void ListMatches(List<string> ListTeam)
{
    if (ListTeam.Count % 2 != 0)
    {
        ListTeam.Add("Bye");
    }

    int numDays = (numTeams - 1);
    int halfSize = numTeams / 2;

    List<string> teams = new List<string>();

    teams.AddRange(ListTeam.Skip(halfSize).Take(halfSize));
    teams.AddRange(ListTeam.Skip(1).Take(halfSize -1).ToArray().Reverse());

    int teamsSize = teams.Count;

    for (int day = 0; day < numDays; day++)
    {
        Console.WriteLine("Day {0}", (day + 1));

        int teamIdx = day % teamsSize;

        Console.WriteLine("{0} vs {1}", teams[teamIdx], ListTeam[0]);

        for (int idx = 1; idx < halfSize; idx++)
        {               
            int firstTeam = (day + idx) % teamsSize;
            int secondTeam = (day  + teamsSize - idx) % teamsSize;
            Console.WriteLine("{0} vs {1}", teams[firstTeam], teams[secondTeam]);
        }
    }
}

que iria imprimir partidas da equipe de cada dia.

Deixe-me rapidamente tentar explicar como o algoritmo funciona:

notei que uma vez que estamos girando todas as equipes, exceto a primeira, se colocarmos todas as equipes em uma matriz, exceto o primeiro, então devemos apenas lido a primeira equipe a partir dessa matriz usando o índice de compensação baseado no dia e fazer aritmética modular para envolver corretamente. Na prática, seria tratar essa matriz como infinitamente repetindo em ambas as direções e nós seria deslizante nosso ponto de vista de forma incremental para a direita (ou à esquerda).

Há um senão, no entanto, e que é o fato de que temos de pedir as equipes de uma forma muito particular para que isso funcione corretamente. Caso contrário, nós não obter a rotação correta. Devido a isso precisamos ler da segunda equipe de correspondência de uma forma muito peculiar também.

A maneira correta para preparar a sua lista é a seguinte:

  • Nunca coloque a primeira equipe (Team # 1) na lista.
  • Tome a última metade da lista de equipe e colocá-los na frente da lista.
  • Tome a primeira metade da lista, invertê-lo e colocá-los na lista (mas não equipe # 1).

Agora, a maneira correta de ler fora da lista é a seguinte:

  • Para cada dia, incrementar o primeiro índice que você está olhando por 1.
  • Para a primeira equipe que você vê naquele local, corresponder à equipe com o Team # 1.
  • Para a próxima equipe na lista ((day + idx) % numDays), que normalmente combiná-lo com a equipe que é compensado pela metade o número de equipes menos 1 (menos 1 porque lidamos com o primeiro jogo nós mesmos). No entanto, desde a segunda metade da nossa lista foi preparada por reverter, precisamos corresponder compensada na segunda metade revertido da lista. A maneira mais simples de fazer é observar que, isso é equivalente a combinando o mesmo índice, mas a partir do final da lista. Dada a day atual offset que é (day + (numDays - idx)) % numDays.

Update 3: I não foi satisfeito que o meu solução envolvido tal selecção convoluto, correspondente, inversão de elementos de matriz. Depois que eu comecei a pensar sobre o que a minha solução envolvida eu percebi que eu estava muito preso a cerca de manter a ordem das equipes como dado. No entanto, isso não é uma exigência e pode-se obter uma programação diferente, mas igualmente válida por não se preocupar com a ordem inicial. Tudo o que importa é o algoritmo de seleção eu descrevo na segunda parte da minha explicação.

Assim, você pode simplificar as seguintes linhas: 

teams.AddRange(ListTeam.Skip(halfSize).Take(halfSize));
teams.AddRange(ListTeam.Skip(1).Take(halfSize -1).ToArray().Reverse());

para: 

teams.AddRange(ListTeam); // Copy all the elements.
teams.RemoveAt(0); // To exclude the first team.

Outras dicas

Parece que você deseja agendar uma torneio round-robin. O artigo wp contém o algoritmo.

Não vejo onde você está mesmo tentando girar a matriz. A permutação será algo parecido com: 1 -> 2 -> 3 -> 4 ... -> n / 2 - 1 -> n - 1 -> n - 2 -> n - 3 -> ... -> n / 2 -> 1 (e 0 estadias fixo). Você pode fazer isso em 2 loops (linha superior e linha inferior).

Eu fiz algumas melhorias no bloco de código respondeu que calcula double cronograma round-robin 

GameEntities db = new GameEntities();


private void btnTeamFixtures_Click(object sender, RoutedEventArgs e)
    {
        txtResults.Text = null;

        var allTeams = db.Team.Select(t => t.TeamName);

        int numDays = allTeams.Count() - 1;
        int halfsize = allTeams.Count() / 2;

        List<string> temp = new List<string>();
        List<string> teams = new List<string>();

        teams.AddRange(allTeams);
        temp.AddRange(allTeams);
        teams.RemoveAt(0);

        int teamSize = teams.Count;

        for (int day = 0; day < numDays * 2; day++)
        {
            //Calculate1stRound(day);
            if (day % 2 == 0)
            {
                txtResults.Text += String.Format("\n\nDay {0}\n", (day + 1));

                int teamIdx = day % teamSize;

                txtResults.Text += String.Format("{0} vs {1}\n", teams[teamIdx], temp[0]);

                for (int idx = 0; idx < halfsize; idx++)
                {
                    int firstTeam = (day + idx) % teamSize;
                    int secondTeam = ((day + teamSize) - idx) % teamSize;

                    if (firstTeam != secondTeam)
                    {
                        txtResults.Text += String.Format("{0} vs {1}\n", teams[firstTeam], teams[secondTeam]);
                    }
                }
            }

            //Calculate2ndRound(day);
            if (day % 2 != 0)
            {
                int teamIdx = day % teamSize;

                txtResults.Text += String.Format("\n\nDay {0}\n", (day + 1));

                txtResults.Text += String.Format("{0} vs {1}\n", temp[0], teams[teamIdx]);

                for (int idx = 0; idx < halfsize; idx++)
                {
                    int firstTeam = (day + idx) % teamSize;
                    int secondTeam = ((day + teamSize) - idx) % teamSize;

                    if (firstTeam != secondTeam)
                    {
                        txtResults.Text += String.Format("{0} vs {1}\n", teams[secondTeam], teams[firstTeam]);
                    }
                }
            }
        }
    }

Se u quer u pode criar 2 métodos e passar e inteiro (Dia) como eu fiz nos 2 linhas comentadas, para separar o código.

Se você tem alguma dúvida ou sugestão não hesite em responder.

pode ser um método complicado, mas este pode ser reduzido a um problema teoria gráfico. Criar um vértice gráfico para cada equipe, e criar uma aresta entre cada vértice (por isso é um grafo completo). Em seguida, para o algoritmo:

Para cada dia de i = 1 .. n:

  • Escolha quaisquer dois vértices não marcados que estão directamente ligados e rotular a borda entre eles com i. Marque ambos os vértices.
  • Repita até que todos os vértices são marcadas.
  • de saída das bordas marcadas (isto é team1 vs team2, Team3 vs Team4 etc)
  • Apagar as bordas marcadas a partir do gráfico e redefinir todos os vértices para não marcado.

Como sobre como calcular as combinações possíveis para cada dia que você quer, então

  1. tipo los dentro de cada par ou seja, menor equipe número é sempre o primeiro em qualquer par.
  2. Ordenar os pares listados para cada dia pelo primeiro em cada par.

Assumindo que temos sempre inclusive equipes número / jogadores (se estranha, adicione BYE; para o meu caso as equipas / jogadores classificados por sua classificação, gostaríamos de ter o topo semeado equipa / jogador para jogar adversário mais fraco primeiro), Aqui é minha implementação. 

void CreateSchedule(int n)
{
    int[] orig = new int[n];
    for(int i=0;i<n; i++){
        orig[i] = i + 1;
    }   
    IEnumerable<int> rev = orig.Reverse();

    int len = orig.Length;
    for (int j = 0; j < len - 1; j++)
    {
        List<int> tmp = new List<int>();
        tmp.Add(orig[0]);
        tmp.AddRange(rev.Take(j).Reverse());
        if (j < len && len > 1 + j) tmp.AddRange(orig.Skip(1).Take(len - 1 - j));
        PrintMe(tmp, j + 1);
    }
}

void PrintMe(IEnumerable<int> arr, int round)
{

    Console.WriteLine("----------Round {0}----------------", round);
    int halfSize = arr.Count() / 2;

    IEnumerable<int> A = arr.Take(halfSize);
    IEnumerable<int> B = arr.Skip(halfSize).Take(halfSize).Reverse();

    var Result = A.Zip(B, (x, y) => $"{x} vs {y}");
    Console.WriteLin(Result);
}
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top