Algoritmus kombinací.

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 “predikátem” buď
A : – pomocí faktoriálů Latex formula
nebo také jinak pomocí
B : – přímmého výpočtu Latex formula

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

U případu A předpokládáme, že knihovna použitého programovacího jazyka obsahuje funkci faktoriál. Tu si pro tento účel nazveme “fact”.
– Deklarujeme proměnnou, která reprezentuje výpočet :
Dim C as double Většinou vystačíme s deklarací integer, nebo single ap.
C = fact(n) / (fact(k)*fact(n-k))

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

U případu B předpokládáme, že programovací jazyk neobsahuje funkci faktoriál. Proto musíme použít numericky přímý výpočet. Ten provedeme pomocí cyklu “for”. Samozřejmě je možné použít také jiný typ cyklu, nebo například skok “GoTo” ap. Samotná syntaxe cyklu for může být odlišná od toho dále uvedeného. Zejména by šlo o rozsah iterací cyklu for tedy 0 To k-1.
– Deklarujeme proměnnou, která reprezentuje výpočet :
Dim C as double Většinou vystačíme s deklarací integer, nebo single ap.
C = 1 Implicitně může být proměnná (číslo) nastavena na “0”, nebo je tato proměnná použita opakovaně – proto může mít jinou, hodnotu, nežli 1 už před spuštěním cyklu. Z toho plyne, že je vždy lepší C postavit na hodnotu 1 před začátekem iterace. (Tím nic nezkazíme a jde také o to, že případnou přednastavenou nulou nemůžeme násobit.)
FOR iCount = 1 TO k
C = C*(
( n – iCount +1) / 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ý.

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)
n1 = n  + 1 – k  ( = n – 2)
n2 = n  + 2 – k  ( = n – 1)
n3 = n  + 3 – k  ( = n – 0)
For k1 = 1 TO n1
—- For k2 = k1+1 TO n2
——– For k3 = k2+1 TO n3
———— C = k1 & ″,″ & k2 & ″,″ & k3 (+ kód zápisu do array)
——– Next k3
—- Next k2
Next k1

Samozřejmě tento algoritmus lze ještě upravit (zmenšit počet řádků). To bychom provedli tak, že n(1-3) bychom proměnné postavili přímo jako horní limitu iterace cyků for. Odpadly by jejich deklarace a specifikace hodnot (3 řádky). Nevedlo by to ale ke zrychlení, protože při každé jednotlivé iteraci by se znovu “horní limity” přepočítávaly. Výše popsaným způsobem se přepočtou jenom 1x na začátku. 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, přepíše proměnné na aktuální hodnotu a uloží do array.
Poznámka :
K čemu je to dobré? No například k triangulaci, nebo ke konkrétmí 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 nejrychleší 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í.

Aby bylo zřejmé co mám na mysli, musím konkretizovat příklad :

Zadání například zní – vytvořit generátor kombinací herního modelu Lotto 49/6, Tedy Combin(49,6) tak aby generoval jen k = 6 s obsahem trojic bez opakování. Znamená to, že v celém souboru řádků (šestic) může být každá různá trojice jen 1x. Teoreticky je k dosažení úkolu potřeba 921 herních tipů – tedy šestic, nebo řádků (termín podle toho co uživatel preferuje).

Iterativní algoritmus stejně jako rekurzivní vygeneruje 1. řádek s podobou 1,2,3,4,5,6.
– U iterativního algoritmu následuje další řádek 1,2,3,4,5,7 až 1,2,4,7,8,9. Celkem tedy 15179 řádků, které jsou vygenerovány a přeskočeny podmínkou, která vyhodnotí průnik (intersect) každého řádku generovaného proti tomu prvnímu řádku. Podmínka je splněna, když intersect (count) < 3. To ale jen pro dva řádky znamená relaci 6 : 6 jednic = 36 relací 1:1. Celkem tedy 546444 zbytečných operací (relací 1:1).
– Naproti tomu rekurzivní algoritmus okamžitě navýší a otestuje 1. trojici z 1,2,3 na 1,2,4. Tedy relace 3:6. Následně testuje 4. číslo. Tam už testuje relaci 4:6 podle schematu :
1,2,4,5 – test = relace 4:6 /teoreticky stačí testovat jen poslední číslo(5) viz poznámka/ Nalezne shodu u první trojice 1,2,5.
1,2,4,6 – test = relace 4:6 /teoreticky stačí testovat jen poslední číslo(6) viz poznámka/ a opět nalezne shodu u první trojice 1,2,6.
Znovu navýší 4. číslo na 1,2,4,7. Opětovně testuje relaci 4:6. Zde už shodu trojice nalézt nelze.
Generátor navýší 5. číslo – 7+1 = 8 a provede kontrolu relací 5:6.
Podobně 6. číslo – 8+1 = 9 a otestuje relaci 6:6.

Je tedy provedeno celkem : relace 3:6 = (3×6)1x, relace 4:6 = (4×6)3x, relace 5:6 = (5×6)1x a relace 6:6 = (6×6)1x. To zanemená součet jednotkových relací 18 + 72 + 30 + 36 = 156. Celkem je při tomto postupu použito 156 – 36 = 120 “zbytečných” operací. Proto zjistíme poměr 546444(iter) : 120(rekurz) = 4553,7. Doslova to znamená, že jen u tohoto druhého řádku je rekurzivní algoritmus 4553,7 x efektivnější nežli algoritmus iterativní. Takové skoky se rychlostí dohnat nedají. Když do iterativního algoritmu zabudujeme obdobné mechanizmy podmínek, dostaneme se k mnohem rozsáhlejšímu kódu, nežli má algoritmus rekurzivní. Pravdou také je, že v případě většího počtu testovaných řádků (generátor postupně přidává řádky do testované množiny) je “vzdálenost” mezi vhodnými tipy (šesticemi) jiná – mnohem menší. Příklad Prvního a druhého tipu hledaného systému je extrémní. Princip výhody však vždy zůstává, byť v míře menší. Podle mých zkušeností se jedná pro tento model C(49,6) přibližně o průměrný efekt 1:70 ve prospěch rekurze. Ale testoval jsem to pouze 1x a od každého druhu algoritmu jen jedním typem. Při tom existuje mnoho variant pro každý kvalitativní druh. Proto tuto hodnotu beru jen jako orientační.
Poznámka :
Efektivnost řešení v tomto případě spočívá v tom, jak je sémanticky koncipována podmínka průniku (intersect). V kódu odkazuji na tuto poznámku. Jde o to, že určitě můžeme vlastní test intersect optimalizovat. Ale pohled jen z příkladu mezi prvním a druhým řádkem je zavádějící. Je to extrém. Při optimalizaci nemůžeme zahrnout všechny odlišnosti do jediné podmínky. Výhodnější je testovat vždy všechna čísla, i když už máme většinu čísel otestovanou. Logika věci ale říká, že řešení (v našem případě hledáme pozitivní shodu 3 čísla) se najde v polovině. Tedy ne při 36. testu (6×6), ale asi v 18. testu – tedy průměrně v polovině. Je sice možné, že by se našlo úplně správné řeší jen pomocí několika řádků kódu, ale nežli riskovat nečekanou chybu je lépe testovat opakovaně. Tento problém je problémem optimalizace. Praktickou cestou je například array řádku rozšířená o 2 hodnoty (sloupce). V jednom se nachází výsledek testu posledního čísla a ve druhém součet všech předchozích včetně toho čísla posledního. Je – li tedy v součtovém sloupci nalezena hodnota 3 (podmínka našeho zadání), pak se zpětně odečte a odznačí poslední číslo. Toto následně nahradíme novým. Tento popis samozřejmě není intersect, tak jak tomu rozumíme z matematiky.
Pří výše vzpomenutém testu jsem ale přímo intersect použil. Test jsem prováděl v prostředí tabulkového procesoru, kde jsem měl fyzicky (vizuálně) zaznamenány vybrané šestice a vedle každé jsem měl sestrojený intersect(count) pomocí maticového vzorce

___________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 (červené operátory podmínek IF) 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í.

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, nebo scriptu, 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.
Téma je velice rozsáhlé už jen po stránce teoretické. O té praktické –  funkčních generátorech – nemluvě. Každý uživatel by chtěl možná něco jiného. Takže ke stažení budou jen pravděpodobně taková obecná makra a scripty. Nevylučuji, že bych někomu později nevyhověl na přání, ale zatím nic takového nechystám. Časem bych zřejmě mohl nabízet i velice specializované programy.

Digiprove sealCopyright secured by Digiprove © 2013 Petr Neudek

Napsat komentář

Přejít k navigační liště