Algoritmus je obecně postup k dosažení daného cíle (účelu). Z tohoto pohledu mají kombinace v rovině účelu 2 druhy algoritmu. Jeden pro vypočtení množství a druhý pro vygenerování vlastní množiny kombinací.

Množina kombinací je vlastně buď „sloupec“, který má na každém řádku jen jedinou položku (buňku). Nejčastěji ve formátu textu (string). Tato textová forma se užívá například pro vygenerování souboru typu CSV, ale můžeme také vytvořit číselnou hodnotu (UV = unique value).

Množina kombinací může být také vytvořena přímo do podoby tabulky, která má pro každý prvek (číslo) k jiný sloupec.

Poznámka :
Jde jen o okamžitou potřebu podoby a tvaru množiny kombinací. Z praktického hlediska většinou vystačíme s vygenerováním CSV souboru a jeho zpětným načtením například do tabulkového procesoru, kde se to změní na vícesloupcovou tabulku.

Algoritmus výpočtu kombinací

Je to struktura určující výpočet – kolik je daných kombinací při zadání konkrétního počtu všech možných n a velikosti výběru k. Ten je dán vzorcem buď A, nebo B : – přímého výpočtu

Generující kód pro případ A

U případu A pomocí faktoriálů C(n,k) = n! / k!*(n-k)!, nebo také jinak pomocí předpokládáme, že knihovna použitého programovacího jazyka obsahuje funkci faktoriál, nebo si ji vytvoříme. Tu si pro tento účel nazveme

Generující kód pro případ B

U případu B (který nemá integrovanou funkci „fact“) : C(n,k) = n*(n-1)*(n-2)*.*.*.*n-(k-1) / k!. Proto musíme použít přímý výpočet. Ten provedeme pomocí některého cyklu, nejlépe „for“.
FOR iCount = 1 TO k
C = C * iCount
NEXT iCount

Algoritmus generátoru množiny kombinací

Na tomto místě musím uvést, že se nejedná ani zdaleka o jediný algoritmus. Je jich až překvapivě mnoho. Tyto algoritmy se dělí na iterativní a nebo rekurzivní. Právě proto na tomto místě uvádím pouze své vlastní algoritmy. Speciálním případem je rekurzivní algoritmus pro vzorce v tabulkových procesorech – určený pro „uživatelské prostředí“. Nejde tedy o programový kód.

Iterativní algoritmus generátoru kombinací

Nejprve musím uvést co výraz iterativní algoritmus znamená. Iterace v programování znamená opakované volání funkce v počítačovém programu, ale můžeme to také vyjádřit jinak jako monotónní funkci. Například připočítávání (inkrementaci, nebo dekrementaci) se stále stejným přírůstkem (nejčastěji po jedné). Také to ale znamená, že při opakované činnosti se nezjišťuje nic o (nebo z) předchozího výsledku. To znamená přímo nejmenší operační náročnost (strojní zatížení). Nepřímo tedy nejvyšší výkon, nebo lépe nejvyšší rychlost zpracování.
Expresivně : Algoritmus bez ohledu na cokoliv jede vpřed. Nic zpětně nezjišťuje a nekontroluje. Je to prostě vystřelená dělová koule.

Iterativním algoritmem není : –

Iterativním algoritmem není automaticky každý postup využívající cyklus for, nebo jiný cyklus (DO, WHILE ap). Pokud je do cyklu vnořen dotaz například IF který testuje něco z, nebo proti předcházejícím výsledkům – pak se jedná o rekurzivní algoritmus.

Iterativním algoritmem je : –

Každý takový, který testuje například generovanou hodnotu na vlastnost s minulými výsledky nesouvisející. Například IF testuje, zda proměnná = Modulo (X) ap. Při splněné podmínce se nalezená hodnota zapíše, v opačném případě přeskočí. Iterátor nesmí být na tomto zjištění závislý. Podobně například cykly bez dotazu. Například zanořené cykly pro kombinace – uvedené dále.

Naznačení iterativního algoritmu. Funkční kód je obsažen v rubrice Algoritmy. Náznak algoritmu je konkretizován na 3. třídu kombinací – tedy k = 3, v obecné rovině je možné postavit 3. třídu kombinací v libovolně větším systému k. To však vyžaduje další kód, který by nám ztížil orientaci v základním kódu. Zadáním požadovaných startovních hodnot můžeme generovat například všechny třídy kombinací od k = 1 do k = 3. Konkrétně se jedná a celou Pascalovu třídu 2^n. Startovní hodnoty všech k(1-3) jsou postaveny na nulu. Nebo můžeme zadat jen startovní hodnoty pro určitou nižší třídu kombinací – například jen 2. třídu k = 2 přestože generátor obsahuje 3 vnořené cykly. Startovní hodnoty jsou potom nastaveny k1=0, k2=1, k3=2. Pro zastavení iterací se použije pomocná proměnná, která inkrementuje na C(n,2), nebo dekrementuje z C(n,2) na nulu.

Pro tento algoritmus bylo zvoleno omezení : maximum n = integer (tedy formátem proměnné (čísla) → praktické omezení počtu všech možných prvků n je pouze na úrovni SW stroje).

Iterativní algoritmus © Petr Neudek 2013

Dim n, n1, n2, n3, k, k1, k2, k3 as integer
Dim C as string (alternativně as double, nebo as array)
n = inputbox (explicitně zadané)
k = inputbox (explicitně zadané k = 3)
For k1 = 1 TO n-2
For k2 = k1+1 TO n-1
For k3 = k2+1 TO n
C = k1 & ″,″ & k2 & ″,″ & k3 (+ kód zápisu do array)
Next k3
Next k2
Next k1

Proto takto zkonstruovaný algoritmus je nepřekonatelně nejrychlejším algoritmem kombinací (konstrukce přímo na míru vyžádané třídě). Je to totiž praktický „holý“ iterátor. Navíc generuje kombinace lexikálně. Při tom nic nefiltruje pomocí funkce Select, nebo IF ap. Nedělá tedy nic jiného, než že provede iteraci, zapíše aktuální hodnotu a uloží do array.
Poznámka :
K čemu je to dobré? No například k triangulaci, nebo ke konkrétní logistické úloze. Aplikací, kde je potřeba velice výkonný algoritmus je mnoho. Nemusí jít vždy jen o dvojice, nebo trojice. Často se setkáme s testy technologických, výrobních, nebo organizačních procesů, které zahrnují interakce mnohem většího počtu kvalitativních parametrů. Existují také velice složitá zadání například v kosmologii, nebo meteorologii a další. Pak už stojí za to hledat nejrychlejší algoritmus. Je toho dosaženo za pomocí specializace na třídu k. Pokud potřebujeme spíš univerzální algoritmus, pak nám může vadit omezení třídou kombinace. Ale jak jsem uvedl výše, lze tento specializovaný algoritmus sestrojit na nejvyšší požadavek k a třídy nižší generovat za pomoci pracovního zastavení cyklů. (Specializovaný algoritmus se zastaví sám). Ale asi i s touto nevýhodou to bude nejrychlejší řešení.

Vlastnosti, které popisuji předurčují použití iterativních algoritmů. Toto použití je poměrně velmi omezené oproti rekurzivním algoritmům. Vhodné jsou prakticky výlučně jen pro konstrukce databází, které se následně zpracují pomocí jiných nástrojů. Tady bych uvedl zejména generování kombinací do podoby „UV“ (unique value). Takto vytvořená unikátní hodnota je velice vhodná pro využití v databázích jako unikátní klíč. Kombinace mají schopnost organizace (orientace) jako lexikální stromy. Současně existuje možnost zápisu kombinací jen pomocí binárního kódu, a proto s nimi lze pracovat také jako s binárními stromy. Více v kapitole kombinatorických konstrukcí.

Rekurzivní algoritmus generátoru kombinací

Nejprve jen zkratkou co je rekurzivní algoritmus. Asi nejlepším popisem (ač zřejmě ne úplně správně vyjádřeno) je výraz algoritmus se zpětnou vazbou. Vhodnějším vyjádřením je skutečnost, že algoritmus se opírá při generování nových hodnot o zpětné kontroly nebo testy hodnot vyjádřených dříve. (Na základě vyhodnocení původních hodnot určí následnou hodnotu.) Z tohoto už spíš pochopíme, oč se jedná. Rekurzivní algoritmy mohou reagovat na větvení. Právě tohle je veliká výhoda oproti tvrdým iterativním algoritmům.

Z toho vyplývá použití pro jednotlivý druh algoritmu. Iterativní algoritmus je vhodný zejména pro vygenerování databáze, která se následně zpracuje jiným programem. Rekurzivní algoritmus je mnohem flexibilnější a hodí se pro úplně všechny možné úlohy. Je sice možné do iterativního algoritmu zařadit filtraci (například pomocí IF ap.), ale efektivnost se výrazně snižuje. S počtem vřazených podmínek se výhoda rychlosti vytrácí přímo neúměrně. Při složitějších zadáních je základ iterativních algoritmů překážkou, která je prakticky diskvalifikuje z okruhu alternativ řešení.

Rekurzivní algoritmus © Petr Neudek 2013

Dim n, k, A, B, C, Ax, Bx, Cx as integer
n = inputbox
k = 3
Dim Lim as double
Lim = Fact(n) / (Fact(k)*Fact(n-k))
For iCount = 1 TO Lim
IF A = 0 AND B = 0 AND C = 0 Then ( pouze při spuštění konkrétní třídy k)
Ax = 1 ( pouze při spuštění konkrétní třídy k)
Bx = 2 ( pouze při spuštění konkrétní třídy k)
Cx = 3 ( pouze při spuštění konkrétní třídy k)
ElseIF A = (n+1-k) AND B = (n+2-k) AND C = (n+3-k) Then
Exit Sub (Stop) (zastavení programu – dojeli jsme na konec)
ElseIf A < (n+1-k) AND B = (n+2-k) AND C = (n+3-k) Then
Ax = A + 1
Bx = A + 2
Cx = A + 3
ElseIf A < (n+1-k) AND B < (n+2-k) AND C = (n+3-k) Then
Ax = A (Specifikace jen pro další účely)
[Bx = B + 1
Cx = B + 2
ElseIf A < (n+1-k) AND B < (n+2-k) AND C < (n+3-k) Then
Ax = A (Specifikace jen pro další účely)
Bx = B (Specifikace jen pro další účely)
Cx = C + 1
End IF
+ kód pro zařazení do : array(row) nebo načtení do proměnné (string, double)
A = Ax (Podstata rekurze – převod generovaných do kontrolovaných hodnot.)
B = Bx (Podstata rekurze – převod generovaných do kontrolovaných hodnot.)
C = Cx (Podstata rekurze – převod generovaných do kontrolovaných hodnot.)
Next iCount

Tento algoritmus je opět jen ilustrační. Je zpracován jako ekvivalent k výše uvedenému iterativnímu algoritmu. Generuje jen systém všech trojic celku n. Při takové úloze lze poměřit druhově různé algoritmy navzájem proti sobě – tedy jen co do rychlosti zpracování. V praxi bychom k takovému účelu (generování databáze) použili algoritmus iterativní. Na tomto rekurzivním algoritmu ale ukazujeme názorně proč je to rekurze. Každému by mělo být zřejmé základní vyhodnocení původních hodnot a také by mohlo být zřejmé, že bez obav vnoříme libovolné množství podmínek na vše, co nás napadne. Místo IF, nebo i spolu s ním použijeme Select. Ve spojení se skokem GoTo dostáváme neuvěřitelnou flexibilitu použití. Samozřejmě podmínky je možné vložit i do iterativního algoritmu, ale ztrácíme tak jeho největší výhodu – rychlost.

Funkční algoritmy jsou nebo postupně budou zveřejněny v rubrice Algoritmy. Tam by se měly objevit také další záležitosti jako vzorce pro tabulkové procesory, odkazy na externí zdroje ap.

V rámci praktických příkladů budou k dispozici funkční sešity Open Office – tedy AOO nebo LO. Nebude to hned. Musím toho hodně napsat. Postupně by ale měl být k dispozici pro každý pojem nejméně 1 praktický příklad generátoru – tedy makra, skriptu, nebo i Extension pro Open Office a jiné.

Na závěr :

V praxi se používá mnoho různých algoritmů. Zejména takové, které nemají omezení třídou k. Samozřejmě také několik takových vlastních mám připraveno. Generují ale jinak nežli ty které zde uvádím. V budoucnu dám všechny typy generátorů k dispozici.