Třídy kombinací

U vzorců kombinací podle této šablony akceptujeme vžité názvosloví. „Třída“ znamená k- člennou kombinaci (počet míst – znaků ve vzestupném uspořádání)

Třída se váže na další pojem „Počet všech možných – značíme ‘n’“. Kombinace je pojem matematický a znamená počet všech různých, k – členných uspořádání z celku všech možných „n“ pro k ? n, kde k – tice je uspořádána „vzestupně“ (též se uvádí, že uspořádání nehraje úlohu ap). Správně k ? n. (též k = „výběr“)

Je – li tedy „k“ podmnožinou „n“ musí mít také jen a pouze unikátní prvky. A také opačně, může li být každý prvek až „k“ krát opakován je n = kn. Nesmysl že?

Dále by se mělo uvádět, že se prvky nesmí opakovat. To se ale neuvádí, protože existují pojmy jako „kombinace s opakováním“. Je to fatální chyba.

Stačí se trošku zamyslet. Je – li množina všech možných „n“ množinou – pak jsou prvky unikátní a stejný prvek stát sám vedle sebe nemůže, natož aby byl v rámci množiny započten více jak 1x. Tento fatální nesmysl se týká také podobně variací s opakováním. Bohu žel učí se to stovky let a zvyk má železnou košili.

Proto raději tuto definici nepoužívejte u zápočtů, či jiných zkoušek. Kombinatorika potřebuje od základu axiomatizovat.

Kombinace byly historicky definovány jako „čísla – obor celých kladných (N)“. V oblasti množin ale musíme definovat „prvky“. Zde nastává malý problém s „uspořádáním prvků“. U „čísel“ je to jasné. Uvědomíme si ale skutečnost, že se jedná o prvky z oboru „N“, které mají své pořadí. Tím ale celá problematika nekončí. Musíme si uvědomit, že například prvek – číslo „3“ je stejně velký jako například prvek – číslo „10“. Tohle pochopil už dávno Euklides. Vlastní velikost „prvku“ = 1.

Tato „velikost“ jedna celá má logickou podstatu z výrazu ?p. Toto čteme jako „Existuje prvek p“ = ano (1). To, co chápeme jako „velikost – 3 ap. 10“ je jen pořadím.

Pořadí je jen „značkou“ stejně jako bychom značili barvou, nebo jiným názvem. Dostáváme se k tomu, že kombinatorika se týká více logiky a množin, nežli klasických kupeckých počtů. Aby toho nebylo málo, je „kombinatorický prvek“ vázán také na logiku existence v čase. Takový prvek spojuje dvojnásobnou logiku existence. Tedy tu obecnou – existuje ano/ne – plus logiku existence v čase a místě – je li prvek ve výběru „k“ není ve zbytku (n-k). Ale všechny prvky existují (pokud existují) ve stejném čase, jen v jiném místě – podmnožině z „n“. Počet kombinací znamená počet „různých výběrů k“. Dva různé výběry nemohou být nikdy a za žádných okolností „současné“. Změní – li se tedy výběr – jeho existence je pravdivá v minulosti – tj (pravda)^0, zatímco současně existující výběr je (pravda)^1.

Když by nebyla akceptována „historická logika existence“ znamenalo by to, že každá kombinatorická množina má jen jediný (současný) výběr. Tedy to za předpokladu, že „v současnosti neexistující výběr“ je nepravda – logicky totiž opravdu neexistuje. Jednotlivé historické, ale již neexistující pravdy jsou intervaly na pomyslné časové ose. Dostali jsme se k pojmu „matematický čas“. Počet kombinací nám tedy nepřímo definuje potenciál množiny času (nikoliv pořadí výběrů) v podstatě jako spodní limitu množství intervalů – potřebných k vyjádření všech různých. S reálným časem to má moc málo společného – ale přece jen něco ano.

Zde uvedené vzorce mají omezení třídou. Naopak prakticky nejsou omezeny množinou všech možných. Limitou pro počet všech možných je omezeno jen HW.

Vzorce mají postaveny limitu zdola na „k“+1, a shora dejme tomu „integer“, nebo „single“. Omezení na „integer“ je provedeno u vzorců generovaných makrem.

Jakmile je ale vzorec vygenerován, platí horní limita podle nastavení tabulkového procesoru. To je v rámci OpenOffice dáno jako „single“.
Dolní limita byla určena proto, že kombinace k-té třídy z „n=k“ = 1 a vzorec, který musí opakovat vstupní řádek je nesmyslný. Horní limita vlastně neexistuje kvůli tomu, že by byly vzorce zatíženy „zbytečnou“ podmínkou. Ve vzorcích se omezení shora nepředpokládá. To je aktuální až u „maker“ kvůli přetečení paměti.

Omezení třídou je sice asi nepříjemné, ale hned na konci tohoto listu je „příklad rozšíření třídy“ si ukážeme jak získat vícečlenné kombinace. Neodpustím si poznámku, že účelem rozšíření – a tedy i šablon je naučit zájemce konstruovat a používat kombinatorické vzorce. Samozřejmě nabízím pomoc i těm, kteří nemají čas, nebo nechtějí studovat postupy z jiného důvodu. Také na to ale budu nahlížet jako na komerční záležitost, nikoliv jako na edukativní.

Návod k používání vzorců :

Vzorce používáme klasicky. Zkopírujeme řádek se vzorci (nikoliv vstupní řádek, tam jsou jen čísla pro nastartování) a kopírujeme směrem dolů jak je libo.

Musíme při tom dávat pozor, abychom nepřetížili HW počítače. Vzorce jsou mnohem objemnější nežli samotná čísla, takže individuálně musíme posoudit kolik toho systém „uveze“ naráz. Řekněme, že to bude 5000 řádků – při třídě kombinací 5 je to 25.000 buněk s aktivním vzorcem. Vzorce po vložení načteme do paměti a vzápětí vložíme zpět jen jako text a čísla (dialog vložit jinak). Vzorce se přepíší na čísla ale jsou stále v paměti, takže přejdeme na konec – řekněme do řádku 5002 a znovu vložíme, tentokrát „normálně“ – nejlépe pomocí Ctrl+V. Opět okamžitě zkopírujeme a vložíme jen „čísla“. Nyní bychom už měli mít vygenerováno 10.000 řádků.

Tento postup můžeme opakovat do té doby, nežli vygenerujeme celou množinu, ale často se stane, že se počítač zpomaluje až by nakonec zamrzl úplně.

Nebo dojdeme až na konec listu (tedy pokud máte opravdu silný stroj).

Často se Vám může stát, že potřebujete vygenerovat mnohem více řádků, nežli snese Váš stroj. To řešíme tak, že při posledním uložení načteme zpět jen o jeden řádek méně (zůstanou v něm vzorce) a zbytek vložíme jen jako hodnoty. Následně vystřihneme poslední dva řádky. Jeden řádek jako hodnoty, protože to bude startovní řádek v novém sešitě. Plus samozřejmě řádek se vzorci. Tyto dva řádky vložíme do nového sešitu, oba sešity uložíme a následně ten původní zavřeme. Tím získáme opět celou kapacitu paměti. Opakujeme postup dokud nedostaneme konec množiny. Ale pozor Vzorce po posledním řádku vygenerují řádek 1.

Co to znamená? Vzorce generují v cyklu. Nemají definovaný „konec“. Samozřejmě určitý „konec“ zaručit lze. Běžně nastavím do poslední + 1 buňky. Hodnotu „0“, nebo text typu „E“ – jako „end“ se smyčkou – pokud je předchozí hodnota „0“ (E), pak opět „0“, nebo „E“. To má ale omezené použití zejména pro „iterace“, ale sledujeme ještě jiný účel.

Spustíme – li kombinace se startovním řádkem „samé nuly“, generujeme schema Pascalova trojúhelníku. Nemůžeme pak zastavovat „na nulu“. Pokud budeme zastavovat například na „E“ může dojít k chybě na makru, protože toto je většinou řízeno číslem, nehledě k tomu, že cyklické opakování je nejvhodnějším kompromisem pro všechny možné účely. Stejně vždy musíme „nějak zastavit“. U vzorců typicky neočekáváme ukončení procesu tak jak to očekáváme u makra.

Vlastní algoritmus uvedených vzorců kombinací je rekurzivní, ale opakující se začátek po konci klasifikuje funkci vzorců jako „iterativní“. Nejsou to shodné pojmy – naopak to jsou pojmy s naprosto opačným významem. Algoritmy rozeznáváme jako iterativní a rekurzivní. Více v listu „Algoritmus“. Jenom bychom si měli uvědomit to, že postup uvnitř vzorce (nebo i makra) – tedy „algoritmus“ je něco jiného, nežli jeho účel. Dále uvádím iterativní algoritmus kombinací.

Dá se aplikovat jen v „makrech“. Všechny ostatní – tedy vzorce podle této šablony a většina „maker“ používá rekurzivní algoritmy a těch je zase poměrně „dost“.

K získání kombinací nemusíme samozřejmě používat jen vzorce uvedené zde v šabloně. Jinou variantou je například „filtrování“ variací, nebo variací s opakováním (správně by se tento pojem používat neměl, ale všichni vědí oč jde). Pak jsou zde makra, která používám, ale znám nejméně 3 různé algoritmy.

Určitě by se jich našlo více, ale nikoliv pro tabulkové procesory. Většina je v jiných jazycích, zejména v „C“, javascriptu a mnoha dalších. Při poměrně rozsáhlé rešerši na internetu jsem nalezl jen jediný tématický „ekvivalent“. Jde taktéž o výukový materiál českého autora který musím pochválit. Avšak k práci v tabulkách se vůbec nehodí. Výsledky jsou dosaženy pomocí maker (psaných funkcí) a „array formula“. To samo už do určité míry limituje počet (kombinací, variací ap) jen na velikost sešitu, nebo jen velikost paměti. Jednotlivé prvky z třídy (tedy celé „k“) je v jediné buňce oddělené separátorem (čárkou). Pro praktickou aplikaci se tedy musí upravit tak, aby jednotlivé prvky byly v samostatných buňkách. To samozřejmě není technický problém, ale jen nepříjemnost. Přes to tento materiál vřele doporučuji. Nevím sice, zda uvedený autor je skutečně autorem. Je možné, že převzal a jen lokalizoval cizojazyčnou verzi. Také bych zdůraznil, že vzorový sešit (sešity) nejsou zaměřeny jen na kombinatoriku, ale na obecnější numerickou analýzu, či spíš na nástroje numerické analýzy, teorie čísel, logiky ap.. Jedná se o tyto stránky : autor: Ing. Petr Pecháček Officír.cz kde je link na zazipované sešity : Excel čísla. Po stažení se rozpakuje foldr ve kterém jsou dva sešity. Jeden z nich obsahuje „kombinatoriku“. Makra z tohoto sešitu (funkce generující maticové výpočty) v OpenOffice nefungují, ale lze je číst v Basicu. Také je vidět názorně jak fungují.

V rámci kapitoly (tento list) a list Algoritmus si ještě ukážeme „intuitivní skládání“ jako základ pro pochopení vnitřních mechanizmů algoritmů. I tuto metodu můžete přímo použít ke konstrukci vícečlenných kombinací a sice bez jakýchkoliv hlubších znalostí práce s tabulkovým procesorem, či dokonce s programováním.

 

Napsat komentář

This site uses Akismet to reduce spam. Learn how your comment data is processed.

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