Tomáš Kot

Generování rozpisu zápasů v systému každý s každým

2. 10. 2006 | Kat.: Různé | Upraveno: 18. 4. 2011 | Přečteno: 25310x | Komentáře: 37

Ilustrativní obrázek k článku Před nějakou dobou jsem narazil na poměrně zajímavý problém - jak vygenerovat rozpis dvojic do jednotlivých zápasů v lize hrané systémem každý s každým tak, aby všechny zápasy byly odehrány v minimálním potřebném počtu kol. Potřebný algoritmus je poměrně jednoduchý, takže si ukážeme, jak se s ním pracuje.

Poznámka duben 2011: děkuji všem za komentáře. Někteří upozorňují na možné nedostatky nebo dokonce chyby v algoritmu, což bohužel nemůžu ověřit, protože již nemám čas do problematiky znovu hlouběji pronikat. Proto prosím všechny případné zájemce, aby brali článek spíše jako inspiraci nebo ukázání cesty a před praktickou aplikací si raději prověřili, jestli dostávají správné výsledky. Za standardních podmínek by algoritmus fungovat měl, v mém případě fungoval.

Rovněž se omlouvám, ale nejsem schopen poskytovat na toto téma konzultace, zejména ne ohledně případných rozšíření algoritmu pro složitější případy. Domnívám se, že kdokoliv z vás bude po přečtení tohoto článku v obraze více než já :) Článek již je několik let starý a já jsem se již generování rozpisů od té doby nikdy nevěnoval.

Nastínění problematiky

Systémem "každý s každým" se hrají základní skupiny nebo i celé turnaje především v různých sportovních odvětvích a nyní například také v online ligách počítačových her.

Podstatou systému je to, že každý tým (hráč, klan - podle toho, zda se jedná o týmový či individuální sport nebo o počítačovou hru) hraje se všemi ostatními daný počet zápasů (většinou jeden). Pokud potřebujeme získat pouze soupis všech vzájemných utkání, je to samozřejmě velmi snadné - stačí si vytvořit tabulku obsahující v záhlaví sloupců i řádků jména všech týmů podle následujícího vzoru (příklad je pro 6 týmů).

Tabulka 1
	1	2	3	4	5	6
1	x	x	x	x	x	x
2	1-2	x	x	x	x	x
3	1-3	2-3	x	x	x	x
4	1-4	2-4	3-4	x	x	x
5	1-5	2-5	3-5	4-5	x	x
6	1-6	2-6	3-6	4-6	5-6	x

Popis tabulky 1: Tabulka všech dvojic týmů pro zápasy každý s každým, příklad pro 6 týmů. Týmy jsou označeny čísly 1 až 6. Zápis A-B vyjadřuje zápas týmu A proti týmu B.

Podobná tabulka nám naprosto postačuje, pokud nezáleží na datu odehrání jednotlivých zápasů. Většinou však je nutné turnaj rozepsat do kol, kdy v každém kole hraje každý tým právě jeden zápas, aby se turnaj odehrál co nejdříve (jestli kolo trvá týden, pak tým hraje jeden zápas týdně) a toto již tak jednoduché není. Při pokusu udělat podobný rozpis "ručně" narazíme zvláště při vysokém počtu týmů na problém, jak pravidelné rozdělení zápasů zajistit.

Trocha matematiky na začátek

Nejdříve si vypočítáme některé více či méně důležité hodnoty. (Ještě poznamenám, že tato a následující kapitola nejsou nezbytně nutné pro aplikaci algoritmu popsaného dále, takže je můžete případně přeskočit.) Jako vstupní údaj nám bude stačit pouze počet týmů účastnících se bojů v dané skupině turnaje - tuto hodnotu označíme n.

Nyní by nás mohl zajímat například celkový počet zápasů, které budou v turnaji odehrány. Ve výše uvedeném příkladu s šesti týmy (n = 6) v tabulce lehce napočítáme 15 zápasů. Obecně k tomuto počtu dojdeme pomocí mezi lidmi ne příliš oblíbené kombinatoriky. V našem případě použijeme operaci nazvanou kombinace bez opakování - potřebujeme vytvořit dvojice z n týmů, přičemž nezáleží na pořadí týmů ve dvojicích. Kombinace bez opakování se počítají pomocí kombinačního čísla, odvozením pro náš případ (dvojice) bychom dostali výsledný výraz pro celkový počet zápasů z (odvození zde není uvedeno, pokud však má někdo o něj zájem, stačí mi dát vědět):

zet = 0,5 krát závorka en méně 1

Vzhledem k tomu, že každý tým bude hrát právě jednou se všemi ostatními, je počet zápasů odehraných jedním týmem (označme t) zřejmý:

té se rovná en méně 1

Sudý a lichý počet týmů

Další výpočty již tak zřejmé nebudou, musíme totiž začít brát v úvahu vliv toho, zda máme lichý nebo sudý počet týmů.

Kdybychom provedli jednoduchou úvahu, že počet zápasů jednoho týmu (t) je roven potřebnému počtu kol turnaje (označme k), protože každý tým má odehrát jeden zápas v každém kole, všechno by bylo v pořádku a rozpis zápasů by se nám podařilo vytvořit - ovšem pouze pokud bude počet týmů (n) sudý.

Pro sudý počet týmů platí, jak již bylo uvedeno, že k = t = n - 1. Počet zápasů v jednom kole (označme s), což je důležitý údaj například pokud se všechny zápasy kola hrají ve stejnou dobu, protože pak určuje potřebný počet "sportovišť" (šachovnic, kurtů, hřišť ...), určíme jednoduchým výpočtem - celkový počet zápasů turnaje z vydělíme počtem kol k:

es = zet lomeno ká = en lomeno 2

Pro lichý počet týmů musíme ale provést malou úpravu. Počet kol bude roven počtu týmů (k = n), přičemž každý tým bude pochopitelně hrát pouze v n - 1 kolech, tzn. v každém kole bude mít jeden z týmů volno. Počet zápasů na kolo určíme podobně jako výše, ale s uvažováním uvedených úprav týkajících se lichého počtu týmů:

es = zet lomeno ká = en méně 1 lomeno 2

Algoritmus pro generování dvojic

Nyní se již dostáváme k vlastnímu algoritmu generujícímu dvojice pro jednotlivé zápasy. I zde se vyskytnou problémy s lichým a sudým počtem týmů, my se však s nimi vypořádáme již nyní na začátku a navíc velmi snadno. Pokud je počet týmů lichý (například 15), budeme prostě uvažovat počet o jedno vyšší (takže místo 15 to bude 16), čímž dostaneme sudý počet a algoritmus se sjednotí. A nebojte se, není potřeba shánět jeden tým navíc i ve skutečnosti. Tento přidaný tým bude totiž pouze "virtuální" a všechny zápasy, ve kterých by měl podle rozpisu hrát, budou jednoduše vypuštěny. Soupeř (již reálně existující) bude tak mít v daném kole volno, jak již bylo zmíněno v předchozí kapitole.

Algoritmus je velmi názorný, protože se dá jednoduše vyjádřit graficky, stačí papír, tužka a následující postup:

1. Týmy si označíme čísly od 1 do n. Pozor - počet týmů n je nyní vždy sudý, tak jak bylo uvedeno na začátku kapitoly!

2. Všechna čísla kromě jednoho pravidelně rozložíme po obvodu kruhu, zbývající číslo (nejvyšší) zapíšeme do jeho středu. Na následujícím obrázku vidíte vzor pro 12 týmů (obrázek je shodný pro skutečný počet týmů 11 i 12), pro jiný počet by se vytvořil obdobně:

Čísla 1 až 11 na kružnici, číslo 12 ve středu

3. Spojíme úsečkou číslo 1 a 12 (nejmenší a největší) a poté dalšími vzájemně rovnoběžnými úsečkami (kolmými na úsečku mezi 1 a 12) spojíme do dvojic všechna ostatní čísla (11-2, 10-3, 9-4, 8-5, 7-6) - viz následující obrázek:

Viz předchozí + úsečky mezi čísly (1-12,11-2,10-3,9-4,8-5,7-6)

4. Jak je asi zřejmé, úsečky označují dvojice pro zápasy, v tomto případě tedy konkrétně pro zápasy prvního kola. Úseček je 6, máme 6 zápasů na kolo. V prvním kole tedy bude hrát tým 1 proti 12, 2 proti 11, 3 proti 10, 4 proti 9, 5 proti 8 a 6 proti 7.

5. Všemi úsečkami společně postupně otáčíme v libovolném (ale stále stejném) směru, čímž dostaneme další dvojice pro jednotlivá kola. V našem případě (12 týmů) je počet kol roven 11, takže otočení provedeme 10krát. Následující tabulka znázorňuje všechny polohy a vypisuje odpovídající zápasové dvojice.

Tabulka 2
Kolo 1: 1-12 11-2 10-3 9-4 8-5 7-6	Kolo 2: 2-12 1-3 11-4 10-5 9-6 8-7	Kolo 3: 3-12 2-4 1-5 11-6 10-7 9-8	Kolo 4: 4-12 3-5 2-6 1-7 11-8 10-9
Kolo 5: 5-12 4-6 3-7 2-8 1-9 11-10	Kolo 6: 6-12 5-7 4-8 3-9 2-10 1-11	Kolo 7: 7-12 6-8 5-9 4-10 3-11 2-1	Kolo 8: 8-12 7-9 6-10 5-11 4-1 3-2
Kolo 9: 9-12 8-10 7-11 6-1 5-2 4-3	Kolo 10: 10-12 9-11 8-1 7-2 6-3 5-4	Kolo 11: 11-12 10-1 9-2 8-3 7-4 6-5

Popis tabulky 2: Tabulka znázorňující postup vytváření zápasových dvojic v jednotlivých kolech. Vždy je uvedeno číslo kola, obrázek s čísly a spojnicemi v odpovídající poloze a nakonec výpis čísel týmů hrajících proti sobě (A-B znamená tým A hrající proti týmu B).

Pokud by byl počet týmů 11 (tedy lichý), byl by uvedený postup stejný, ale zápasy proti týmu číslo 12 by se nehrály, protože tým 12 neexistuje. Soupeř by měl v daném kole volno.

Naprogramování algoritmu

Popsaný algoritmus má kromě názorného grafického použití i další výhodu - dá se jednoduše naprogramovat do libovolného jazyka a využít tak pro automatické generování rozpisu zápasů. Například na internetových stránkách libovolné ligy či turnaje je možno po ukončení webové registrace hráčů okamžitě zveřejnit rozpis zápasů. Ten se vytvoří pomocí PHP nebo ASP skriptu.

V jazyce PHP je možno algoritmus zapsat následovně:


<?php

  function je_liche($cislo) {

    return(bool)($cislo & 1);

  }



  function GenerujRozpis($pocet_tymu) {

    if (je_liche($pocet_tymu))

      $n = $pocet_tymu + 1;

    else

      $n = $pocet_tymu;

      

    $k = $n - 1; // počet kol

    $s = $n / 2; // počet zápasů na kolo

  

    for ($i = 1; $i <= $k; $i++) {

      if (!je_liche($pocet_tymu))

        $zapasy[$i][] = $i . "-" . $n;

      for ($j = 1; $j < $s; $j++) {

        $tym_a = (($n - $j + $i - 2) % $k) + 1;

        $tym_b = (($i + $j - 1) % $k) + 1;

        $zapasy[$i][] = $tym_a . "-" . $tym_b;

      }

    }

    return $zapasy;

  }

?>

V kódu jsou nadefinovány dvě funkce. První z nich je pouze pomocná a slouží k určení, zda je číslo liché. Druhá funkce (GenerujRozpis) zajišťuje vlastní generování rozpisu. Vstupní hodnotou je počet týmů (může být i lichý, jedná se o skutečný počet!) a návratová hodnota funkce je pole obsahující seznam všech utkání rozdělených do jednotlivých kol. Následující příklad ukazuje způsob vytvoření a jednoduchého vypsání rozpisu pro 11 týmů:


<?php

  $rozpis = GenerujRozpis(11);

  foreach ($rozpis as $kolo=>$zapasy) {

    echo "<h3>Kolo $kolo:</h3>";

    foreach ($zapasy as $dvojice) 

      echo "<p>$dvojice</p>";

  }

?>

Celou PHP aplikaci si můžete vyzkoušet přímo v prohlížeči nebo stáhnout zdrojový kód (zip 1,11 kB).

V prostředí Visual Basic 2005 je programový kód obdobný, samozřejmě s jinou syntaxí a některými drobnými úpravami vynucenými rozdílností jazyků:


Function JeLiche(ByVal cislo As Integer)

  Return CBool((cislo And 1))

End Function



Function GenerujRozpis(ByVal PocetTymu As Integer) As String(,)

  Dim n, k, s, i, j, TymA, TymB As Integer

  If JeLiche(PocetTymu) Then

    n = PocetTymu + 1

  Else

    n = PocetTymu

  End If

  

  k = n - 1 'počet kol

  s = n / 2 'počet zápasů na kolo

  Dim Zapasy(k, s - 1) As String

  

  For i = 1 To k

    If Not JeLiche(PocetTymu) Then Zapasy(i, 0) = i & "-" & n

    For j = 1 To s - 1

      TymA = ((n - j + i - 2) Mod k) + 1

      TymB = ((i + j - 1) Mod k) + 1

      Zapasy(i, j) = TymA & "-" & TymB

    Next

  Next

  Return Zapasy

End Function

Hotovou VB.NET aplikaci si rovněž můžete vyzkoušet (exe 32,0 kB). Zdrojové soubory pošlu na požádání.

Související odkazy

Popis systému každý s každým (Wikipedie, anglicky)
Kombinatorika, úvod (Wikipedie)
Testovací PHP stránka algoritmu (tom-kot.cz)
Zdrojový kód PHP skriptu (tom-kot.cz, ZIP)
Ukázková aplikace (Visual Basic 2005) (tom-kot.cz, EXE)

Autor: Tomáš Kot | Seznam článků

Komentáře článku

immirtygument | 06.01.2012, 03:50:24

The basic specie standard rule floating exchange rate can insulate loans fast cash flexibility to conduct. France, the principal bimetallic nation, had large enough reserves of both metals to continue nineteenth century a transformation the gold standard game e.g. effective both between countries Bretton Woods Gold Exchange began commitment mechanism, its enduring fame is as. on gold in the provid
fedokesse | 12.11.2011, 08:24:35

What about the English invent football championship?
b0SamueL0b | 10.09.2011, 02:15:14

+z$8frZdyL%68pSU/:>w<:E3.lG-!XIB
neutr | 01.08.2011, 11:01:55

Poměrně dobré, ale to co tady většinou popisujete jako své potřeby není na algoritmus. Ten je nutno udělat pro každou množinu a různé podmínky znovu a jinak. Já řeknu, že jde o typické rozpisy, které se konstruují jen 1x a není co řešit. Se sudým počtem prvků je to tak, že se množina dvojic rozdělí do podmnožin jednic. Těchto podmnožin je o jednu méně, nežli je počet prvků sudé množiny. Lichá množ
Petr | 02.05.2011, 20:50:35

Ahoj, nemohl by přepsat někdo algoritmus v programovacím jazyce C? Děkuji.
martin | 12.04.2011, 17:20:54

Obávám se, že má autor v prográmku chybu. Pokud zadáte počet týmů např. 6, tak tým číslo 6 je vždy jako druhý (hostující).
Lubor | 23.03.2011, 22:02:05

Ahojte, hele... já mám v rozenou blbou vlastnost, že když vidím vzoreček, tak si ho sám vyzkouším v praxi a pokud možno se snažím sám zjistit jeho podstatu, abych si ho v případě, že ho zapomenu mohl sám "vymyslet"...
To samé jsem udělal i tady a divím se, že na to nikdo nedošel - chtěl bych autora upozornit, že v kapitole "Sudý a lichý počet týmů" musí mít u druhého vzorce překlep. s=z/n, ne
cialis | 14.03.2011, 20:29:55

Une liste des sites de casino en ligne francais parmi les return populaires de l'annee 2011. Sur quel casino en ligne la plupart des francais jouent-ils ?
Zdenda | 24.02.2011, 18:17:06

Čau, spustil jsem web na generování rozpisů na online-generator-rozpisu.g6 tecka cz.
Jirka | 02.02.2011, 14:32:22

Ahoj, článek je super. Pro tento případ se dají použít i známé "Bergerovy tabulky", ale to co postrádám já i více pisatelů tady je určit pořadí jednotlivých zápasů na jednodenních turnajích, hraných na jednom čí více hřištích tak, aby prodlevy mezi jednotlivými zápasy byly pro všechny přibližně stejné. Já jsem řešil jednodenní turnaj, kde byly čtyři skupiny po 8 hráčích hráno ne třech hřištích.
f0llower | 30.11.2010, 14:45:34

Marek jednoducho, toto pridáš pred skript:
$team[1] = "Sparta";
$team[2] = "Slavia";
$team[3] = "Baník";
atd.

nájdeš si potom tento riadok:
echo "<li>tým $tym1 - tým $tym2</li>";

a upravíš ho na:
echo "<li>tým $team[$tym1] - tým $team[$tym2]</li>";
Jiří | 24.09.2010, 19:01:53

Již nějakou dobu hledám nějaký rozpis turnaje. Vaše stránka je pěkná jestli Vás mohu poprosit o vytvoření rozpisu pro 8 týmů na turnaj v nohejbale odehrát se musí během jednoho dne a na jednom hřišti něco jsme již vytvořili, ale některá mužstva mají dlouhou přestávku nehrají i 6 zápasů pak třeba každý druhý zápas jestli je možnost sladit hru alespoň s přestávkou tak 3 až 4 zápasy.Děkuji Jelínek
LiborBes | 14.09.2010, 17:52:44

C# prepis:

public static string[,] GenerujRozpis(int pocetTymu)
{
int n = JeLiche(pocetTymu) ? pocetTymu + 1 : pocetTymu;
int k = n - 1; // počet kol
int s = n / 2; // počet zápasů na kolo

string[,] zapasy = new string[k + 1, s];

for (int i = 1; i <= k; i++)
{
if (!JeLiche(pocetTymu))
zapasy[i, 0] = i.ToString() + "-" + n.ToString();

for (int j = 1; j < s; j++
jiří | 18.08.2010, 10:46:04

mám vymyslet systém deblového tenis-turnaje pro 12 dvojic tak, aby se hráči točili uvnitř dvojic a hráli vždy s jinými. díky J.
petr | 22.03.2010, 02:03:19

ahojky v jednom předmetu zabývající se optimalizací bych chtěl udělat rozpis utkání, algoritmus každý s každým jsem našel zde, ale potřeboval bych ještě nák zakomponovat rozhodčí a hriště a hrací čas, existuje na to taky nějaký algoritmus na netu jsem nic nenašel :( díky
Ruby | 03.03.2010, 00:02:04

...safra, to oříznutí jsem nečekal....
... tedy rozhodně nechtěl. Zkoušel jsem kolo "rozkývat", ale není to k ničemu, navíc 12ka bude druhá vždycky... Třeba někoho něco napadne.
Každopádně ještě jednou díky za inspiraci.
Ruby | 02.03.2010, 23:59:15

Tak s něčím takovým se (marně) morduju už třetí den. Mohlo mě napadnout, že už to někdo vymyslel... a přitom to vypadá tak jednoduše :-) Díky za inspiraci. Kód je opravdu elegantní. Jenom poznámka - v rozpisu postrádám střídání pozice domácí/host. Uvedení v pozici s sebou zpravidla nese pro domácí výhodu (třeba u hokeje poslední volbu hráčů při střídání). Takže podle tohohle rozpisu bych 12ku mít
Miro | 02.03.2010, 13:45:20

Pekný deň , perfekná stránka. Lámem si hlavu ako prerozdelit 5 muzstiev kazdy s kazdym,jedná sa o mladeznicky hokejový turnaj...Je mozne mi vytvorit celkovu tabulku? az do finále? diiikkk
Vlasta | 01.03.2010, 13:00:44

Super, to jsem si urychlil práci :-)
stanislav | 26.10.2009, 23:12:33

každá hra trvá 40min. a máme na to jen 6hod. Potom už to ty starší pány nebaví.Dá se vymyslet systém jak na to. Dík stašek
stanislav | 26.10.2009, 23:07:00

je nás 12 a chceme hrát turnaj v marijáši každy s každým. Nechceme však aby turnáj trval 10hod. Prosím o pomoc s rozpism.
stašek
stanislav | 26.10.2009, 23:06:59

je nás 12 a chceme hrát turnaj v marijáši každy s každým. Nechceme však aby turnáj trval 10hod. Prosím o pomoc s rozpism.
stašek
Jan Borýsek | 27.08.2009, 07:29:19

Mám stejný problém jako můj předchůdce,
turnaj a není možno se připojit na web. Pokud je možno zaslat budu vděčný. Děkuji
Maroš Hrabčák | 05.06.2009, 12:32:38

Dá Váš program stiahnúť a uložiť do počítača? Organizujeme turnaj a potrebujeme ho hneď v konkrétny deň kde nie je prístup na internet a ešte nevieme koľko družstiev príde. Pošlite mi ho , Ďakujem
janko | 22.03.2009, 17:52:01

Pekny clanok, ale chyba tomu par veci k dokonalosti...
Chyba tam "odveta" - ked hram s niekym doma, tak s nim budem hrat aj vonku
2 - neda sa tam nijako dosadit napr nazvy timov, aby to vygenerovalo napr Slavia - Sparta
Zlin - Kladno

atd .. dufam ze to doplnis :)
demag | 28.02.2009, 13:33:35

Ahoj peknej clanek mam podobnej problem jak rozlozit 11 lidi do ctveric aby hral kazdy s kazdym
vko | 11.12.2008, 13:08:09

Ahoj, díky moc. Tvoje poznatky využijeme při pořádání ligy FIFA09. Marně jsme si lámali hlavu a teď.......nezbývá než poděkovat.
Nipaba | 04.11.2008, 22:00:37

Jen čtenost tohoto článků říká že je dobrý a s tím souhlasím. Nicméně bych se chtěl zeptat na to samé co Marek ... Dá se tam vložit ID_týmu :-)
Vaníček | 21.10.2008, 06:59:56

Chtěl bycha autorovi moc a moc poděkovat. Program na rozpis zápasů je SUPER. Je za tím spousta práce, tak alespoň poděkování. Je vidět, že lidé co něco znají jsou mezi námi. Dík
hudi | 01.09.2008, 17:57:58

pekny clanek je to skoro co som hladal az ne jeden problem da sa tento program upravit aj na pocet sportovišť" (šachovnic, kurtů, hřišť ...)? povedzme ze mame 10 hracov ale iba 4 sportoviska potom bude viac kol a aj viac hracov bude stat. co potom?
czkoudy | 12.07.2008, 18:36:33

Hezký článek,
já bych potřeboval, aby to generovalo i odvety. Tzn. pro 4 týmy by bylo 6 zápasů, 3 tak jak píše vaše fce a 3 zápasy s prohezenými pozicemi.Šlo by to?
Belo | 18.05.2008, 16:06:05

Perfektný článok, vysvetlené úplne do podrobna, ušetril si mi dost vela času, dik. :)
roman2 | 22.01.2008, 21:51:21

Super,přesně to, co jsem hledal,díky.
Lupa | 16.11.2007, 21:53:21

uzasny, naprosto perfektne vysvetleno... diky moc ;)
Honza | 18.02.2007, 10:17:19

Nadhera, byl jsem linej nad tim premyslet a tohle je presne to co jsem hledal :-)
Marek | 13.11.2006, 05:09:50

No jo, já vím že jsem lama.:) Ale můžeš mi prozradit, jak dosadím za proměnný $tym1 a $tym2 třeba id_tymu co mám v databázi v tabulce? :)
24k | 24.10.2006, 12:44:17

Pěkný článek, už takovou fci vlastním, nicméně pokud tento web bude pokračovat takovýmito radami, budu sem chodit i nadále :-)