Trocha té kombinatoriky

pro stolní a karetní hry

Kombinatorika, zejména kombinace a permutace, hrají klíčovou roli při tvorbě herních komponent, ať už jde o karetní, deskové či digitální hry. Pomáhají vytvářet vyvážené, strategické a variabilní herní systémy.

Proč je to důležité? Porozumění kombinacím a permutacím umožňuje systematicky navrhovat herní mechaniky, zajistit spravedlivé rozložení prvků a definovat úroveň náhody. Bez těchto principů může hra působit nevyváženě nebo příliš náhodně, což snižuje herní zážitek.

V praxi se kombinace využívají například při designu karetních balíčků. U set-collection her je zásadní, aby byly kombinace symbolů či vlastností rozloženy promyšleně, čímž se zajistí jejich rovnoměrná dostupnost. Například hra 7 divů světa využívá pečlivě vyváženou distribuci karet, která umožňuje různé strategie bez rizika „slepých míst“ v herním obsahu.

Permutace jsou naopak klíčové tam, kde záleží na pořadí prvků. Například pořadí karet v balíčku ovlivňuje dynamiku hry, a správné promíchání může pomoci optimalizovat herní tok. Hry, které pracují s draftováním nebo sekvenčním pořadím akcí, využívají permutace k vytvoření napětí a strategie.

Příklad využití permutací lze ilustrovat v karetní hře, kde má každá karta tři barevné oblasti a jednotlivé barvy se nesmí na stejné kartě opakovat. Hráč se snaží sestavit kvarteto karet tak, aby se na určité pozici vytvořil jednobarevný pruh. Díky systematickému rozložení permutací je zajištěno, že každá barva se vyskytuje na všech pozicích rovnoměrně, čímž je umožněno hráčům budovat různé strategie bez rizika, že by některá kombinace nebyla v balíčku zastoupena. To zvyšuje variabilitu hry a minimalizuje frustraci z nevyváženého rozložení karet.

Použití kombinatoriky v herním designu umožňuje vytvářet strukturované, vyvážené a zábavné hry. Hráči oceňují, když hra nabízí logickou strukturu a strategickou hloubku. Designér díky tomu nemusí spoléhat jen na intuici, ale může vědomě pracovat s množstvím, variabilitou a interakcemi herních prvků. To vede k vyšší znovuhratelnosti a lepšímu hernímu zážitku.

Kombinatorika tedy není jen teoretický koncept, ale praktický nástroj, který pomáhá vytvářet hry, jež mají pevný rámec a dávají hráčům smysl. Díky ní mohou být herní mechaniky bohatší a herní zážitky hlubší.

Množiny a výběry z nich

Faktoriál

Faktoriál je základ k pochopení kombinatoriky!

Faktoriál čísla n (značený n!) je součin všech přirozených čísel od 1 do n. Používá se v kombinatorice, například pro výpočet permutací.
Příklad:
5! = 5 × 4 × 3 × 2 × 1 = 120
To znamená, že pokud máme 5 různobarevných kuliček (červená, modrá, zelená, žlutá a fialová) v pytlíku a chceme zjistit, kolika jedinečnými způsoby je lze vytáhnout z pytlíku a uspořádat do řady, použijeme faktoriál. Na první pozici můžeme vytáhnout a položit jakoukoli z pěti kuliček, protože v tu chvíli jsou v pytlíku všechny. Na druhou pozici ale už máme možnost vytahovat jen ze čtyř zbývajících barev, protože první barevná kulička už je venku a do pytlíku se nevrací. Na třetí pozici už můžeme vytáhnout jen jednu ze zbývajících tří kuliček atd. Tento princip vede k tomu, že celkový počet možných pořadí (permutací) je právě 5! = 120.

Klíčová vlastnost faktoriálu je, že 0! = 1.

I když se to může zdát zvláštní, dává to smysl z kombinatorického hlediska – existuje právě jeden způsob, jak neuspořádat nic (prázdná posloupnost). Tento fakt je také důležitý v matematických vzorcích, kde zachovává konzistenci výpočtů.

Permutace

Předpokládáme, že záleží na pořadí barev na kartě a barvy se nesmí opakovat. Proto počítáme permutace bez opakování, které se vypočítají vzorcem:

P(n, k) = n! / (n – k)!

Vysvětlení hodnot v tabulce:

• Sloupce (k): Představují počet pozic na kartě (trojice, čtveřice, pětice).
• Řádky (n): Představují počet barev, které jsou k dispozici pro výběr.
• Hodnoty v tabulce: Každá hodnota v tabulce udává celkový počet různých jedinečných karet, které je možné vytvořit pro danou kombinaci počtu barev (n) a počtu pozic (k), za předpokladu, že záleží na pořadí a barvy se nesmí opakovat.

Kombinace

Tentokrát je tu tabulka pro kombinace bez opakování. V tomto případě nezáleží na pořadí barev na kartě a barvy se na jedné kartě nesmí opakovat. Použijeme tedy vzorec pro kombinace bez opakování:

C(n, k) = n! / (k! * (n – k)!)

Vysvětlení hodnot v tabulce:

• Sloupce (k): Představují počet pozic na kartě (trojice, čtveřice, pětice).
• Řádky (n): Představují počet barev, které jsou k dispozici pro výběr.
• Hodnoty v tabulce: Každá hodnota v tabulce udává celkový počet různých skupin karet, které je možné vytvořit pro danou kombinaci počtu barev (n) a počtu pozic (k), za předpokladu, že na pořadí nezáleží a barvy se nesmí opakovat.

Když neznáš Python, dej do toho mateřštinu

1. Variace s opakováním (Pořadí záleží, Opakování povoleno):

Pro variace s opakováním je to nejjednodušší. Pro každou pozici v sekvenci prostě iterujeme přes všechny dostupné prvky.

Předpokládejme, že máme množinu prvků prvky = ['A', 'B', 'C'] a chceme vytvořit variace délky k = 3.

Pseudokód s vnořenými cykly by vypadal takto:

variace_s_opakovanim = []
prvky = ['A', 'B', 'C']
k = 3

pro i1 v prvky:
  pro i2 v prvky:
    pro i3 v prvky:
      variace = [i1, i2, i3]
      variace_s_opakovanim.pripoj(variace)

vytiskni variace_s_opakovanim

Vysvětlení:

• Vnořené cykly: Používáme tolik vnořených for cyklů, jaká je délka variace (k=3 v tomto případě, tedy 3 vnořené cykly).
• Iterace přes všechny prvky v každém cyklu: V každém cyklu (i1, i2, i3) iterujeme znovu přes celou množinu prvky. To umožňuje, aby se prvky v rámci variace opakovaly.
• Vytvoření variace a uložení: V nejvnitřnějším cyklu vytvoříme seznam variace obsahující aktuální kombinaci prvků z cyklů a uložíme ji do seznamu variace_s_opakovanim.

Výsledek pro prvky = ['A', 'B', 'C'] a k = 3 by byl:

[['A', 'A', 'A'], ['A', 'A', 'B'], ['A', 'A', 'C'], ['A', 'B', 'A'], ['A', 'B', 'B'], ['A', 'B', 'C'], ['A', 'C', 'A'], ['A', 'C', 'B'], ['A', 'C', 'C'], ['B', 'A', 'A'], ['B', 'A', 'B'], ['B', 'A', 'C'], ['B', 'B', 'A'], ['B', 'B', 'B'], ['B', 'B', 'C'], ['B', 'C', 'A'], ['B', 'C', 'B'], ['B', 'C', 'C'], ['C', 'A', 'A'], ['C', 'A', 'B'], ['C', 'A', 'C'], ['C', 'B', 'A'], ['C', 'B', 'B'], ['C', 'B', 'C'], ['C', 'C', 'A'], ['C', 'C', 'B'], ['C', 'C', 'C']]

2. Variace bez opakování (Pořadí záleží, Opakování NEpovoleno):

Pro variace bez opakování musíme zajistit, aby se v rámci jedné variace prvek nemohl objevit vícekrát. To můžeme udělat tak, že si v každém cyklu pamatujeme, které prvky jsme už použili. Jednodušší a efektivnější přístup je ale pracovat s indexy a v každém vnořeném cyklu iterovat jen přes zbývající nepoužité prvky. V pseudokódu je ale názornější ukázat přístup s explicitním sledováním použitých prvků.

variace_bez_opakovani = []
prvky = ['A', 'B', 'C']
k = 3

pro i1 v prvky:
  pouzite_1 = [i1] # Sledujeme použité prvky v prvním cyklu
  zbyvajici_1 = [p pro p v prvky kdyz p neni v pouzite_1] # Zbývající prvky pro 2. cyklus
  pro i2 in zbyvajici_1:
    pouzite_2 = pouzite_1 + [i2] # Sledujeme použité prvky v prvních dvou cyklech
    zbyvajici_2 = [p pro p v prvky kdyz p neni v pouzite_2] # Zbývající prvky pro 3. cyklus
    pro i3 in zbyvajici_2:
      variace = [i1, i2, i3]
      variace_bez_opakovani.pripoj(variace)

vytiskni variace_bez_opakovani

Vysvětlení:

• Sledování použitých prvků: V každém cyklu si vytváříme seznam pouzite_x prvků, které už byly použity v předchozích cyklech.
• Výběr zbývajících prvků: Pro každý cyklus vytváříme seznam zbyvajici_x prvků, které nebyly dosud použity, pomocí list comprehension a podmínky if p not in pouzite_x.
• Iterace jen přes zbývající: V každém vnořeném cyklu iterujeme pouze přes zbyvajici_x prvky, čímž zajistíme, že se prvek v rámci jedné variace nemůže opakovat.
• Vytvoření variace a uložení: Stejně jako u variací s opakováním, v nejvnitřnějším cyklu vytvoříme variaci a uložíme ji.

Výsledek pro prvky = ['A', 'B', 'C'] a k = 3 by byl:

[['A', 'B', 'C'], ['A', 'C', 'B'], ['B', 'A', 'C'], ['B', 'C', 'A'], ['C', 'A', 'B'], ['C', 'B', 'A']]

3. Kombinace bez opakování (Pořadí NEzáleží, Opakování NEpovoleno):

Pro kombinace bez opakování potřebujeme zajistit nejen vyloučení opakování prvků, ale i zrušení závislosti na pořadí. To znamená, že například kombinace [‚A‘, ‚B‘, ‚C‘] a [‚B‘, ‚A‘, ‚C‘] se považují za stejné. Můžeme toho dosáhnout tak, že v cyklech zajistíme, aby se prvky vybíraly v rostoucím pořadí indexů (pokud prvky nějak indexujeme). Opět ukážu pseudokód s explicitním sledováním indexů.

Předpokládejme, že máme prvky indexované jako prvky = ['A', 'B', 'C'] s indexy 0, 1, 2.

kombinace_bez_opakovani = []
prvky = ['A', 'B', 'C']
k = 3
n = delka(prvky)

pro i1_index v rozsah(n): # Cyklus pro 1. prvek - indexy od 0 do n-1
  pro i2_index v rozsah(i1_index + 1, n): # Cyklus pro 2. prvek - indexy od i1_index+1 do n-1
    pro i3_index v rozsah(i2_index + 1, n): # Cyklus pro 3. prvek - indexy od i2_index+1 do n-1
      kombinace = [prvky[i1_index], prvky[i2_index], prvky[i3_index]]
      kombinace_bez_opakovani.pripoj(kombinace)

vytiskni kombinace_bez_opakovani

Vysvětlení:

• Indexové cykly: Cykly i1_index, i2_index, i3_index iterují přes indexy prvků v množině prvky, ne přes samotné prvky.
• Rostoucí pořadí indexů: Klíčové je nastavení rozsahů cyklů:
  • i1_index jde od 0 do n-1.
  • i2_index jde od i1_index + 1 do n-1.
  • i3_index jde od i2_index + 1 do n-1.
  • Tímto nastavením zajistíme, že v každé kombinaci budou indexy prvků vždy v rostoucím pořadí. Například, pokud i1_index = 0, i2_index už nikdy nebude 0 ani menší, ale jen 1, 2, … , n-1. A i3_index už bude vždy větší než i2_index.
• Vyloučení opakování a pořadí: Tímto způsobem automaticky vylučujeme jak opakování prvků, tak i různé pořadí stejných prvků. Například, pokud bychom generovali kombinaci obsahující prvek na indexu 0, 1 a 2, nikdy se nestane, že bychom vygenerovali kombinaci s indexy 1, 0, 2, protože druhý index i2_index je vždy větší než první index i1_index.
• Vytvoření kombinace a uložení: V nejvnitřnějším cyklu vytvoříme kombinaci pomocí indexů (prvky[i1_index], prvky[i2_index], …) a uložíme ji.

Výsledek pro prvky = ['A', 'B', 'C'] a k = 3 by byl:

[['A', 'B', 'C']]

Poznámka: Pro k=2 by byl výsledek: [['A', 'B'], ['A', 'C'], ['B', 'C']]

4. Kombinace s opakováním (Pořadí NEzáleží, Opakování POVOLENO):

Kombinace s opakováním jsou nejkomplexnější. Opět musíme zajistit nezávislost na pořadí a zároveň povolit opakování prvků. Můžeme to udělat modifikací přístupu z kombinací bez opakování, ale s tím, že rozsahy cyklů budou mírně jiné, aby se povolilo opakování a zároveň zachovalo rostoucí pořadí indexů.

kombinace_s_opakovanim = []
prvky = ['A', 'B', 'C']
k = 3
n = delka(prvky)

pro i1_index v rozsah(n): # Cyklus pro 1. prvek - indexy od 0 do n-1
  pro i2_index v rozsah(i1_index, n): # Cyklus pro 2. prvek - indexy od i1_index do n-1 (VŠIMNI SI ZMĚNY!)
    pro i3_index v rozsah(i2_index, n): # Cyklus pro 3. prvek - indexy od i2_index do n-1 (VŠIMNI SI ZMĚNY!)
      kombinace = [prvky[i1_index], prvky[i2_index], prvky[i3_index]]
      kombinace_s_opakovanim.pripoj(kombinace)

vytiskni kombinace_s_opakovanim

Vysvětlení (Změny oproti kombinacím bez opakování):

• Rozsahy cyklů: Změna je v rozsazích vnořených cyklů i2_index a i3_index. Místo rozsah(i1_index + 1, n) a rozsah(i2_index + 1, n) používáme rozsah(i1_index, n) a rozsah(i2_index, n).
  • i2_index in rozsah(i1_index, n): Druhý index i2_index nyní může být stejný jako i1_index, nebo větší. To povoluje opakování prvku vybraného v prvním cyklu.
  • i3_index in rozsah(i2_index, n): Třetí index i3_index může být stejný jako i2_index nebo větší. To povoluje opakování prvku vybraného v druhém cyklu.
• Rostoucí nebo stejné indexy: Nastavení rozsahů cyklů rozsah(i1_index, n), rozsah(i2_index, n), rozsah(i3_index, n) zajistí, že v každé kombinaci budou indexy prvků v neklesajícím pořadí (rostoucí nebo stejné). To vylučuje závislost na pořadí a zároveň povoluje opakování prvků.
• Vytvoření kombinace a uložení: Stejně jako v předchozích případech, v nejvnitřnějším cyklu vytvoříme kombinaci pomocí indexů a uložíme ji.

Výsledek pro prvky = ['A', 'B', 'C'] a k = 3 by byl:

[['A', 'A', 'A'], ['A', 'A', 'B'], ['A', 'A', 'C'], ['A', 'B', 'B'], ['A', 'B', 'C'], ['A', 'C', 'C'], ['B', 'B', 'B'], ['B', 'B', 'C'], ['B', 'C', 'C'], ['C', 'C', 'C']]

Poznámka: Pro k=2 by byl výsledek: [['A', 'A'], ['A', 'B'], ['A', 'C'], ['B', 'B'], ['B', 'C'], ['C', 'C']]