PARTITION NUMERORUM

Tento pojem má velice jednoduchý princip. Dnes pod tímto pojmem zkráceným na „partition“ rozumíme zejména diskové oddíly, což je pouze nejfrekventovanější aplikace z mnoha různých.

K zavedení pojmu Partitio Numerorum došlo před rokem 1905, kdy Planck rozluštil problém světelného záření černého tělesa pomocí kvantové teorie. Více Milan Kunz. Také Partition number theory nebo Partiton of a set.

Partitio Numerorum (PN) je množina všech možných různých součtů na číslo n.

Pojem pochází z kvantové hypotézy fyzika Ludvíka Boltzmanna v roce 1870. Ve snaze dokázat svou rovnici pro termodynamickou entropii, uvedl příklad rozdělení 7 kvant energie mezi 7 částic :

  1. 7
  2. 6+1
  3. 5+2
  4. 5+1+1
  5. 4+3
  6. 4+2+1
  7. 4+1+1+1
  8. 3+3+1
  9. 3+2+2
  10. 3+2+1+1
  11. 3+1+1+1+1
  12. 2+2+2+1
  13. 2+2+1+1+1
  14. 2+1+1+1+1+1
  15. 1+1+1+1+1+1+1

Existuje 15 možných rozdělení, které chápeme jako vektory s klesajícími čísly. Někdy se v této souvislosti hovoří o orbitách, ale nejčastěji rozumíme právě rozdělení na díly. Odtud je také odvozen název. V rámci kombinatoriky budeme hovořit o rozložení n do n-tic.

Když se podíváme pozorně na schema které zveřejnil Ludvík Boltzmann, povšimneme si typického rozvoje od největšího zahuštění k nejmenšímu. Uvědomujeme si, že je to schema entropie (jak jinak Boltzmann schema sestrojil jako vyjádření entropie). To vytváří asociaci ke kosmologii, respektive k rozložení energie ve vesmíru. Pokud použijeme PN jako základ přirozené množiny n = k2, dostaneme představu o rozložení nejen energie, ale i hmoty.

Přestože je schema „orbit“ řazeno sestupně podle největší n-tice, v průběhu rozvoje se objevují pasáže, které jsou typické pozvolným přibýváním počtu podmnožin a náhlého (skokového) zmenšení počtu (zahuštění). To se děje při přestupu tříd (počtu podmnožin) a mohli bychom to ztotožnit s rozpínáním vesmíru, při současné kumulaci hmoty v hvězdách a černých dírách. Respektive podmíněného rozpínání a opaku, tedy zahušťování hmoty působením gravitace.

Existuje teorie MOND (Modified Newtonian Dynamics), respektive gravitace na základě entropie, kterou uvedl Erik Verlinde. Projev rozvoje PN více, či méně koresponduje s teorií Erika Verlindeho, což je teoretický fyzik, který se zabývá teorií strun. Nejvíce šokoval v roce 2009, kdy představil svou entropickou teorii gravitace. Gravitaci v této teorii nepovažuje za samostatnou sílu, ale za typickou entropickou sílu, která je způsobena gradientem informace. (Já bych osobně upřednostňoval přibližně tvrzení, že mikrosvět i makrosvět se řídí matematikou jako rozvoj PN, respektive rozvojem PŘIROZENÉ MNOŽINY).

Význam PN pro matematiku

Význam PN v rámci algebry, respektive matematiky popisuje například článek pojednávající o polynomech – například zde : Gaussova enumerace. Pojmem PN se asi nejvíce zabývá teorie čísel. PN je celkem logicky uváděno do souvislosti s kombinatorikou, ale nikoliv jako základní pojem.

Zřejmě se nikde neuvádí, že PN je vlastně stejně jako faktoriál unární množinou, a tyto jsou základem pro operace v kombinatorice. Ostatní pojmy jako kombinace, variace a permutace jsou množiny binárních prvků (nesprávně uváděných jako binární množiny).

Význam PN v aplikacích

Genetika – například PN(2) = (2, 1+1) má zřejmě souvislost s dědičností a vystačí se dvěma chromozomy u lidí. Ale rozmnožování jiných druhů může mít více pohlaví zejména ve formě hermafroditů. Některé druhy nepotřebují dvojici jedinců ke svému rozmnožení. Jiné druhy potřebují dvojici, ale tito jedinci mohou být stejného pohlaví.

Savci mezi něž patří i lidé mají pohlaví definováno dvěma chromozomy. Ženy XX a muži XY. PN(2) tedy vystačí jen pro některé živočišné druhy. V rámci flóry i fauny se často objevuje více druhů pohlaví. Víme, že i u lidí se čas od času vyskytnou jedinci s oběma pohlavními orgány, ale tito jsou většinou neplodní. To jsou mutace, které pokládáme za chybu kódu. Některé rostlinné i živočišné druhy se rozmnožují cíleně v jiných počtech pohlaví.

Příroda zřejmě reaguje na vnější podmínky života a umožňuje proto i rozmnožování jen jedním jedincem, nebo se dočasně jeden z dvojice se stejným pohlavím změní na opačný. Takže se nabízí vysvětlení, že například lidská homosexualita je součástí přirozeného vývoje a stejně tak výskyt obou pohlavních orgánů u jedince. Byly prováděny pokusy na krysách přemnožených v uzavřeném prostoru s dostatkem vody i jídla. Po přemnožení se začalo vyskytovat „homosexuální“ chování. Logicky se tak příroda snaží zastavit růst populace. V případě nedostatku jídla by došlo ke kanibalizmu.

Nabízí se otázka proč existuje převaha chromozomu X. Proč se nevyskytuje uspořádání v celém spektru variací 22? Tedy XX, XY, YX, YY, nebo jinak X2 + 2XY + Y2? Z pohledu kombinací, nebo lépe z řádku Pascalova trojúhelníku 22 = součet kombinací C(0,2) + C(1,2) + C(2,2). Když si to převedeme ze vzorců na koeficienty, je to 1+2+1.

Hmyzí říše nabízí takové uspořádání, například včely. Specializovaná královna, kterou oplodňují trubci a většina populace jsou dělnice, které se nemohou reprodukovat. Přes to se někdy z dělnic při rojení vytvoří královny. Vidíme, že matka je v roji jediná, potřebuje hodně trubců, aby naplnila své poslání a ještě více dělnic. To vysvětluje převahu ženského chromozomu. U lidí je tomu jinak, ale X zůstává preferovaným chromozomem. Omezení počtu chromozomů Y je zřejmě výsledkem evolučního vývoje, kterým je zajišťováno, aby nebylo rozmnožování podmíněno existencí armády specializovaných jedinců. Praktické minimum jsou dva jedinci pro případ potřeby zastoupit partnera, který je dočasně omezen péčí o potomstvo. Tím je zajištěna také podmíněná diverzifikace dědičné informace. Pokud by nedocházelo k mísení genofondu, docházelo by k znehodnocení vlastností až ke stavu, kdy jedinec nemůže naplnit svoje potřeby a druh vyhyne. Armáda specializovaných jedinců má také horší podmínky pro zachování života. Dvojice pro reprodukci je zřejmě optimálním řešením, které pomáhá adaptaci na velice rozličná prostředí.

Význam pro kombinatoriku

Zde se jedná o oblast výpočtů, ale také o axiomatizaci kombinatoriky prostřednictvím množin. Existuje uspořádání pojmů podle počtu takto : k, n, PN(n), C(n), F(n), V(n), P(n).

Konkrétně :

  1. k = Výběr z možných, například k (0, 1 … , 7)
  2. n = počet možných, například n = 7
  3. PN(n) Partitio Numerorum PN(7) = 15
  4. 2n Kombinace (Pascalův řádek pro 27) = 128
  5. F(n) Faktoriál jako V(7,7) = 7! = 5040
  6. k!*C(k,n) Variace jako Σ 0!*C(0,7) + 1!*C(1,7) + … + 7!*C(7,7) = 13700
  7. P(n) Permutace PN(7)*F(7) = 75600.

Při tom k, n jsou čísla oboru N, PN(n) + F(n) jsou unární množiny, C(k,n), V(k,n) a P(k,n) jsou množiny binárních prvků. Otázka pojmů s opakováním je detailně řešena v kapitole Přirozená množina, kde tyto uvádíme jako nekauzální.

Problém axiomatizace kombinatoriky spočívá zejména na pojmu množin s binárními prvky. Teorie množin zná jen unární prvky, proto je nesprávné uvádět kombinace, variace a permutace jako „binární množiny“. U množin předpokládáme různé prvky (tečky, kroužky) čtverečky, hrušky švestky, … , ale vždy unikátní a unární.

V rámci množin jsou bezesporné pouze k, n, PN(n), F(n). Z praxe víme, že existují množiny binárních a větších prvků. Pod binárními prvky si můžeme představit mince, nebo hrací kostky jako prvky heximální a podobně. Právě toto svádí k definicím pojmů s opakováním, což je nesmysl – žádné prvky se neopakují. Jde veskrze o podmnožiny první třídy. Binární prvek C(1,2), heximální prvek C(1,6). Například 3 hrací kostky obsahují potenciálně 3*6 čísel, ale výběr je omezen na počet C(1,6)3, tedy určitý (poslední) případ PN(18) zjištěného jako n = 3*6 z výrazu pro kombinace C(3,18), vztah je potom C(1,6)3 ⊂ C(3,18), konkrétně 216 ⊂ 816, což je 26,47 % z celku.

Dostáváme s k tomu, že jak pojmy s opakováním, tak pojmy s vícečlennými prvky vyjádříme pouze pomocí faktoriálu (ve tvaru kombinací), což je unární množina, ačkoliv vzorec kombinací už používá dva druhy operací, tedy násobení plus dělení a tím jsou kombinace klasifikovány jako neunární množina. Unární množiny PN(n) a F(n) jsou základem pro výpočetní postupy a tedy také pro definice všech ostatních pojmů kombinatoriky.

Praktické použití

Pro představu, nebo i praktické použití přidávám odkaz na soubory PN od PN(2) až PN(100) zde :

PN(100), PN(99), PN(98), PN(97), PN(96), PN(95), PN(94), PN(93), PN(92), PN(91), PN(90), PN(89), PN(88), PN(87), PN(86), PN(85), PN(84), PN(83), PN(82), PN(81), PN(80), PN(79), PN(78), PN(77), PN(76), PN(75), PN(74), PN(73), PN(72), PN(71), PN(70), PN(69), PN(68), PN(67), PN(66), PN(65), PN(64), PN(63), PN(62), PN(61), PN(60), PN(59), PN(58), PN(57), PN(56), PN(55), PN(54), PN(53), PN(52), PN(51), PN(50), PN(49), PN(48), PN(47), PN(46), PN(45), PN(44), PN(43), PN(42), PN(41), PN(40), PN(39), PN(38), PN(37), PN(36), PN(35), PN(34), PN(33), PN(32), PN(31), PN(30), PN(29), PN(28), PN(27), PN(26), PN(25), PN(24), PN(23), PN(22), PN(21), PN(20), PN(19), PN(18), PN(17), PN(16), PN(15), PN(14), PN(13), PN(12), PN(11), PN(10), PN(9), PN(8), PN(7), PN(6), PN(5), PN(4), PN(3), PN(2).

PN(0) je mimo definici, PN(1) je pouze jeden řádek s jedničkou. Teprve PN(2) má dva řádky a stojí (relativně a spíš z principu) za to uvádět jako množinu (respektive tabulku).

PN roste docela rychle s rostoucím n, ale faktoriál roste rychleji. Například PN(100) obsahuje počet 190 569 292 řádků. Když si stáhnete soubor ve formátu 7-ZIP a rozbalíte ho, dostanete adresář který obsahuje více jak 19 tisíc souborů CSV každý s 10 tisíci řádků.

Soubory CSV neobsahují záhlaví tabulky, a jsou primárně určeny pro import do tabulkového procesoru, který záhlaví nepotřebuje, a který nabízí více možností, nežli jiné aplikace. Proto vysvětlíme co se v souborech objevuje a proč.

V prvním sloupci je pořadové číslo z generátoru od 1 do 190569292. Ve druhém sloupci je třída řádku. Tříd je samozřejmě 100. Ve třetím sloupci je pomlčka – sloupec je určen k pracovním poznámkám, proto je na začátku, aby byl vždy vidět. Do tohoto sloupce si můžeme udělat poznámku při hledání, nebo vkládat vzorce pro vyhledávání. Od čtvrtého sloupce začínají vlastní tvary PN jako čísla, tedy 4. sloupec první číslo, a tak dál. Podle toho jak je mohutné n.

Počet sloupců počínajíc od čtvrtého je shodný s počtem n i když žádný mimo posledního řádku nevyužívá všechny sloupce. Místo záznamu je tam nula. Důvodem je možnost provádět poznámky za posledním sloupcem, protože stačí stisknout Ctrl+šipku doprava a stojíme na konci řádku, proto nuly až do konce, aby poznámky byly pod sebou ve stejném sloupci.

Záhlaví tam není kvůli snížení počtu řádků, ale nuly naopak zvyšují nároky na stroj, což je trošku v rozporu. Vše je postaveno tak, aby bylo umožněno pohodlné přizpůsobení databáze.

Zde se dostáváme k tomu, že někteří uživatelé budou preferovat uspořádání podle tříd (stejného počtu podmnožin), nebo naopak nativní uspořádání z generátoru kde vyhledáváme podle největšího čísla v prvém sloupci databáze (sloupec číslo 4) atd.

Prohledávat databázi se sto milionem řádků není snadné a požadavky budou velice různorodé. Předpokládám, že uživatelé budou mít zájem sami si databázi uspořádat tak jak jim vyhovuje. Vytvoří si například samostatný soubor pro každou třídu, nebo pro stejné číslo v prvním sloupci. Někdo si bude chtít vytvořit záhlaví například kvůli importu do některého databázového systému a sloučí listy do větších souborů. Někdo jiný bude preferovat práci v tabulkovém procesoru za pomoci skriptů (maker) a může mu vyhovovat stávající uspořádání. Jiný uživatel si CSV převede například do XML databáze, nebo upřesní název pro rychlé iterace vyhledávání mezi soubory.

Doporučený postup při vyhledávání zejména více parametrů naráz. Nejlépe tedy makrem, ale postup lze aplikovat i manuálně pomocí vzorců. Například budeme prohledávat databázi za účelem zjištění trojúhelníků. Těch je více druhů. Tedy pravoúhlé, rovnoramenné, rovnostranné, nebo podobné, či ostatní obecné. Každý řádek může obsahovat více různých sledovaných parametrů, takže potřebujeme pro každý parametr jiný sloupec výsledků.

Manuálně můžeme každý jednotlivý parametr zadat jako vzorec do sloupce C (pozitivní výsledek jako značku, negativní výsledek jako dvě uvozovky ““, což je prázdná buňka). Vzorec vykopírujeme od prvního řádku do posledního. Výběr je stále aktivní C1:C10000 a hned ho zkopírujeme do paměti. Skočíme nakonec souboru (Ctrl+END) a přesuneme se na první (nebo další) sloupec za původně posledním sloupcem. Pomocí Ctrl+šipka nahoru se dostaneme do prvého řádku, kam zkopírujeme výsledky už jen jako čísla, nebo text. Následně použijeme vzorec pro vyhledávání dalšího parametru, který stejným způsobem použijeme v dalším sloupci na konci souboru.

Takto získáme všechny hledané parametry. Naposledy skočíme na konec Ctrl+END, držíme Ctrl a stiskneme HOME. Celý soubor včetně sloupců s výsledky je vybrán a nyní jej seřadíme podle sloupců s výsledky. Řádky obsahující výběr zkopírujeme a vložíme do souboru který obsahuje jen pozitivní výsledky v některém sloupci parametru. Soubor s výsledky uložíme, ale pracovní list databáze zavřeme bez uložení (všechny naše vstupy zmizí – zůstane jen původní stav) a otevřeme další.

Při manuální obsluze bych doporučoval skrýt všechny řádky mimo prvního a posledního, plus skrýt sloupce AB (do C kopírujeme vzorce) a dále D až poslední sloupec aby v náhledu zůstaly pouze dva řádky a několik málo sloupců (sloupec C plus sloupce parametrů). Při dobré znalosti práce se vzorci a klávesovými zkratkami je postup snadný.

Samozřejmě takto obsloužit 19 tisíc souborů pro PN(100) je práce za trest a nejspíš se nám nevyhne chyba. Ale dobře postavené makro na stejném, nebo podobném principu a na jediné kliknutí je nejlepším řešením. Manuální postup by šel realizovat pro mnohem menší n nežli je 100.

Licenční ujednání : Odkázané soubory můžete používat bez omezení.

Napsat komentář

Tato stránka používá Akismet k omezení spamu. Podívejte se, jak vaše data z komentářů zpracováváme..

Translate »