Algorytm planowania dla turnieju round-robin?

Question

Niedawno studiowałem różne rzeczy i spotkałem się z Donaldem Knuthem. Ale nie znalazłem odpowiedniego algorytmu do mojego problemu.

Problem Mamy ligę z n graczami. co tydzień mają mecz ze sobą. w ciągu n-1 tygodni każda drużyna walczyła ze sobą. jest n/2 meczów dziennie. ale jedna drużyna może walczyć tylko raz w tygodniu. jeśli wygenerujemy kombinację (n/k), otrzymamy wszystkie kombinacje... (zakładając k = 2), ale muszę ustawić je we właściwej kolejności.

Moja pierwsza sugestia nie była... najlepsza. właśnie utworzyłem tablicę, a następnie niech komputer spróbuje, jeśli znajdzie właściwą drogę. jeśli nie, wróć do początku, przetasuj tablicę i zrób to jeszcze raz, cóż, zaprogramowałem to w PHP (n=8) i to, co wychodzi, działa, ale zajmuje to dużo czasu, a dla n=16 daje mi limit czasu także.

Pomyślałem więc, czy może znajdziemy algorytm, albo ktoś zna książkę, która omawia ten problem.

A oto mój kod: http://pastebin.com/Rfm4TquY

algorithm combinatorics

25

Philipp Spiess 11 lipiec 2011, 14:01

6

Zobacz Wikipedię

–

Gareth Rees

11 lipiec 2011, 14:34

1

Po prostu dodaję ten komentarz tutaj, ponieważ ten temat wydaje się być właściwym miejscem do przekazania kilku ciekawskich facetów do tego powiązanego tematu w Codereview.

–

Redu

6 luty 2020, 20:19

Answer 1

Klasyczny algorytm działa tak:

Ponumeruj drużyny 1..n. (Tu wezmę n=8.)

Napisz wszystkie drużyny w dwóch rzędach.

1 2 3 4
8 7 6 5

Kolumny pokazują, które drużyny zagrają w tej rundzie (1 vs 8, 2 vs 7, ...).

Teraz napraw 1, ale rotuj wszystkie inne zespoły. W drugim tygodniu otrzymujesz

1 8 2 3
7 6 5 4

A w 3 tygodniu otrzymujesz

1 7 8 2
6 5 4 3

Trwa to przez tydzień n-1, w tym przypadku

1 3 4 5
2 8 7 6

Jeśli n jest nieparzyste, zrób to samo, ale dodaj fikcyjną drużynę. Każdy, kto zostanie dopasowany do obojętnej drużyny, otrzyma w tym tygodniu pożegnanie.

69

Wolf 3 luty 2015, 18:54

Answer 2

Oto kod tego w JavaScript.

function makeRoundRobinPairings(players) {
  if (players.length % 2 == 1) {
    players.push(null);
  }

  const playerCount = players.length;
  const rounds = playerCount - 1;
  const half = playerCount / 2;

  const tournamentPairings = [];

  const playerIndexes = players.map((_, i) => i).slice(1);

  for (let round = 0; round < rounds; round++) {
    const roundPairings = [];

    const newPlayerIndexes = [0].concat(playerIndexes);

    const firstHalf = newPlayerIndexes.slice(0, half);
    const secondHalf = newPlayerIndexes.slice(half, playerCount).reverse();

    for (let i = 0; i < firstHalf.length; i++) {
      roundPairings.push({
        white: players[firstHalf[i]],
        black: players[secondHalf[i]],
      });
    }

    // rotating the array
    playerIndexes.push(playerIndexes.shift());
    tournamentPairings.push(roundPairings);
  }

  return tournamentPairings;
}

AKTUALIZACJA: Naprawiono błąd zgłoszony w komentarzach

5

varun 19 maj 2020, 12:13

Widzę błąd z kodem @varun. Używając: ['a','b','c','d'] [Runda 1] 0: {p1: "a", p2: "c"} 1: {p1: "a", p2: " b"} [Runda 2] 0: {p1: "a", p2: "d"} 1: {p1: "b", p2: "c"} [Runda 3] 0: {p1: "a", p2: "a"} 1: {p1: "c", p2: "d"}

–

There

17 maj 2020, 23:48

Jeśli chodzi o błąd w kodzie @varun, to go naprawia: CHANGE "let playerIndexes = player.slice(1).map((, i) => i);" TO "let playerIndexes = p.map((, i) => i); playerIndexes.shift();"

–

There

18 maj 2020, 00:04

Answer 3

Zrobiłem zaktualizowane rozwiązanie z funkcjami wielokrotnego użytku (zainspirowane przez varun):

const testData = [
  "Red",
  "Orange",
  "Yellow",
  "Green",
  "Blue",
  "Indigo",
  "Violet",
];

const matchParticipants = (participants) => {
  const p = Array.from(participants);
  if (p % 2 == 1) {
    p.push(null);
  }
  const pairings = [];
  while (p.length != 0) {
    participantA = p.shift();
    participantB = p.pop();
    if (participantA != undefined && participantB != undefined) {
      pairings.push([participantA, participantB]);
    }
  }
  return pairings;
};

const rotateArray = (array) => {
  const p = Array.from(array);
  const firstElement = p.shift();
  const lastElement = p.pop();
  return [firstElement, lastElement, ...p];
};

const generateTournament = (participants) => {
  const tournamentRounds = [];
  const rounds = Math.ceil(participants.length / 2);
  let p = Array.from(participants);
  for (let i = 0; i < rounds; i++) {
    tournamentRounds.push(matchParticipants(p));
    p = rotateArray(p);
  }
  return tournamentRounds;
};

console.log(generateTournament(testData));

1

Joe Sadoski 15 kwiecień 2021, 02:34

Answer 4

Zrobiłem ten kod, odnośnie wyjaśnienia Okasaki

const roundRobin = (participants) => {
  const tournament = [];

  const half = Math.ceil(participants.length / 2);
  const groupA = participants.slice(0, half);
  const groupB = participants.slice(half, participants.length);
  groupB.reverse();

  tournament.push(getRound(groupA, groupB));


  for(let i=1; i < participants.length - 1; i ++) {
    groupA.splice(1, 0, groupB.shift());
    groupB.push(groupA.pop())
    tournament.push(getRound(groupA, groupB));
  }

  console.log(tournament)
  console.log("Number of Rounds:", tournament.length)
  return tournament;
}

const getRound = (groupA, groupB) => {
  const total = [];
  groupA.forEach((p, i) => {
    total.push([groupA[i], groupB[i]]);
  });
  return total;
}

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

P.S.: Podałem przykład z nieparzystą kwotą, więc drużyna nie gra w każdej rundzie, pojedynkuje się z undefined, można to dostosować tak, jak chcesz

0

Dr.G 15 listopad 2021, 20:21

Algorytm planowania dla turnieju round-robin?

4 odpowiedzi

Podobne pytania

Powiązane pytania

Nowe pytania

algorithm