Kombinatorický číselný systém - Combinatorial number system

v matematika, a zejména v kombinatorika, kombinatorický číselný systém stupně k (pro nějaké kladné celé číslo k), označovaný také jako kombinované látky, je korespondence mezi přirozená čísla (zahrnuto včetně 0) N a k-kombinace, zastoupená jako přísně klesá sekvence C_k > ... > C₂ > C₁ ≥ 0. Jelikož posledně jmenované jsou řetězce čísel, lze to považovat za určitý druh číselná soustava za reprezentaci N, ačkoli hlavní nástroj představuje a k-kombinace N spíše než naopak. Zřetelná čísla odpovídají odlišným k-kombinace a produkovat je lexikografický řád; navíc čísla menší než ${ displaystyle { tbinom {n} {k}}}$ odpovídají všem k-kombinací { 0, 1, ..., n − 1}. Korespondence nezávisí na velikostin ze sady, kterou k-kombinace jsou převzaty z, takže to může být interpretováno jako mapa z N do k-kombinace převzaty z N; v tomto pohledu je korespondence a bijekce.

Číslo N souhlasí s (C_k,...,C₂,C₁) darováno

{ displaystyle N = { binom {c_ {k}} {k}} + cdots + { binom {c_ {2}} {2}} + { binom {c_ {1}} {1}}. }

Skutečnost, že jedinečná sekvence tak odpovídá libovolnému číslu N byl pozorován uživatelem D. H. Lehmer.^[1] Opravdu a chamtivý algoritmus najde k-kombinace odpovídající N: vzít C_k maximální s ${ displaystyle { tbinom {c_ {k}} {k}} leq N}$ , pak vezměte C_{k − 1} maximální s ${ displaystyle { tbinom {c_ {k-1}} {k-1}} leq N - { tbinom {c_ {k}} {k}}}$ , a tak dále. Nalezení čísla Npomocí výše uvedeného vzorce z k-kombinace (C_k,...,C₂,C₁) je také známý jako „hodnocení“ a opačná operace (daná chamtivým algoritmem) jako „nehodnocená“; tyto operace jsou většinou známy pod těmito jmény systémy počítačové algebry a v výpočetní matematika.^[2]^[3]

Původně používaný termín „kombinatorická reprezentace celých čísel“ je zkrácen na „kombinatorický číselný systém“ o Knuth,^[4]kdo také dává mnohem starší odkaz;^[5]termín „kombinovaný“ zavádí James McCaffrey ^[6] (bez odkazu na předchozí terminologii nebo práci).

Na rozdíl od systém číselných faktorů, kombinatorický číselný systém stupně k není smíšený radix systém: část ${ displaystyle { tbinom {c_ {i}} {i}}}$ čísla N reprezentovaný "číslicí" C_i se z ní nezíská pouhým vynásobením místní hodnotou.

Hlavní aplikací systému kombinatorických čísel je, že umožňuje rychlý výpočet k-kombinace, která je na dané pozici v lexikografickém pořadí, aniž byste museli explicitně uvádět k-kombinace předcházející; to umožňuje například náhodné generování k-kombinace dané sady. Výčet k-kombinace má mnoho aplikací, mezi nimiž testování softwaru, vzorkování, kontrola kvality a analýza loterie hry.

Objednávkové kombinace

A k-kombinace sady S je podmnožinou S s k (odlišné) prvky. Hlavním účelem kombinatorického číselného systému je poskytnout reprezentaci, vždy pomocí jediného čísla, ze všech ${ displaystyle { tbinom {n} {k}}}$ možný k-kombinace sady S z n elementy. Výběr pro všechny n, {0, 1, ..., n − 1} jako takový soubor, to může být uspořádáno, že reprezentace daného k-kombinace C je nezávislá na hodnotě n (Ačkoli n musí být samozřejmě dostatečně velký); jinými slovy zvažuje C jako podmnožina větší množiny zvýšením n nezmění číslo, které představujeC. Pro kombinatorický číselný systém tedy člověk jen uvažuje C jako k-kombinace sady N všech přirozených čísel bez výslovného uvedení n.

Aby bylo zajištěno, že čísla představující k-kombinací {0, 1, ..., n − 1} jsou menší než ti, kteří zastupují k-kombinace, které nejsou obsaženy v {0, 1, ..., n − 1} k-kombinace musí být uspořádány takovým způsobem, aby byly nejprve porovnány jejich největší prvky. Nejpřirozenější uspořádání, které má tuto vlastnost, je lexikografické objednávání z klesající sled jejich prvků. Takže porovnání 5 kombinací C = {0,3,4,6,9} a C'= {0,1,3,7,9}, jeden to má C přijde dříve C', protože mají stejnou největší část 9, ale další největší část 6 z C je méně než další největší část 7 C'; lexikograficky porovnávané sekvence jsou (9,6,4,3,0) a (9,7,3,1,0). Dalším způsobem, jak popsat toto uspořádání, je zobrazit kombinace jako popisující k zvýšené bity v binární reprezentaci čísla, takže C = {C₁,...,C_k} popisuje číslo

{ displaystyle 2 ^ {c_ {1}} + 2 ^ {c_ {2}} + cdots + 2 ^ {c_ {k}}}

(toto přiřadí různá čísla k Všechno konečné množiny přirozených čísel); pak srovnání k-kombinaci lze provést porovnáním přidružených binárních čísel. V příkladu C a C„odpovídají číslům 1001011001₂ = 601₁₀ a 1010001011₂ = 651₁₀, což opět ukazuje C přijde dříve C'. Toto číslo však není tím, které chce zastupovat k-kombinace s, protože mnoho binárních čísel má počet zvýšených bitů odlišných od k; jeden chce najít relativní polohu C v objednaném seznamu (pouze) k-kombinace.

Místo kombinace v objednávce

Číslo přidružené v kombinatorickém číselném systému stupňů k do a k-kombinace C je počet k-kombinace přísně menší než C v daném objednání. Toto číslo lze vypočítat z C = { C_k, ..., C₂, C₁ } s C_k > ... > C₂ > C₁ jak následuje. Z definice objednání vyplývá, že pro každého k-kombinace S přísně méně nežC, existuje jedinečný indexi takhle C_i chybí S, zatímco C_k, ..., C_i+1 jsou přítomni v Sa žádná jiná hodnota větší než C_i je. Lze je tedy seskupit k-kombinace S podle možných hodnot 1, 2, ..., k z ia počítat každou skupinu zvlášť. Pro danou hodnotu i jeden musí zahrnovatC_k, ..., C_i+1 v Sa zbývající i prvky S musí být vybráno z C_i nezáporná celá čísla přísně menší než C_i; navíc každá taková volba povede k k-kombinace S přísně méně nežC. Počet možných možností je ${ displaystyle { tbinom {c_ {i}} {i}}}$ , což je tedy počet kombinací ve skupině i; celkový počet k-kombinace přísně menší než C pak je

{ displaystyle { binom {c_ {1}} {1}} + { binom {c_ {2}} {2}} + cdots + { binom {c_ {k}} {k}},}

a toto je index (počínaje od 0) z C v objednaném seznamu k-kombinace. Je zřejmé, že je pro každého N ∈ N přesně jeden k-kombinace na indexuN v seznamu (předpokládejme k ≥ 1, protože seznam je pak nekonečný), takže výše uvedený argument dokazuje, že každý N lze zapsat přesně jedním způsobem jako součet k binomické koeficienty daného tvaru.

Nalezení k-kombinace pro dané číslo

Daný vzorec umožňuje najít místo v lexikografickém pořadí daného k-kombinace okamžitě. Opačný proces hledání k-kombinace na daném místě N vyžaduje trochu více práce, ale přesto je přímočará. Podle definice lexikografického uspořádání dva k-kombinace, které se liší svým největším prvkem C_k budou seřazeny podle porovnání těchto největších prvků, z čehož vyplývá, že všechny kombinace s pevnou hodnotou jejich největšího prvku jsou v seznamu souvislé. Navíc nejmenší kombinace s C_k jako největší prvek je ${ displaystyle { tbinom {c_ {k}} {k}}}$ a má C_i = i - 1 za všechny i < k (pro tuto kombinaci všechny výrazy ve výrazu kromě ${ displaystyle { tbinom {c_ {k}} {k}}}$ jsou nula). Proto C_k je největší počet takových ${ displaystyle { tbinom {c_ {k}} {k}} leq N}$ . Li k > 1 zbývající prvky k-kombinace z k − 1-kombinace odpovídající číslu ${ displaystyle N - { tbinom {c_ {k}} {k}}}$ v kombinatorickém číselném systému stupňů k − 1, a lze je tedy najít pokračováním stejným způsobem pro ${ displaystyle N - { tbinom {c_ {k}} {k}}}$ a k − 1 namísto N a k.

Příklad

Předpokládejme, že chceme určit kombinaci 5 na pozici 72. Postupné hodnoty ${ displaystyle { tbinom {n} {5}}}$ pro n = 4, 5, 6, ... jsou 0, 1, 6, 21, 56, 126, 252, ..., z nichž největší do 72 je 56, pro n = 8. Proto C₅ = 8 a zbývající prvky tvoří 4 kombinaci na pozici 72 − 56 = 16. Postupné hodnoty ${ displaystyle { tbinom {n} {4}}}$ pro n = 3, 4, 5, ... jsou 0, 1, 5, 15, 35, ..., z nichž největší do 16 je 15, pro n = 6, takže C₄ = 6. Podobně pokračujeme v hledání 3 kombinace na pozici 16 − 15 = 1 jeden najde C₃ = 3, který spotřebuje finální jednotku; toto stanoví ${ displaystyle 72 = { tbinom {8} {5}} + { tbinom {6} {4}} + { tbinom {3} {3}}}$ a zbývající hodnoty C_i budou maximální s ${ displaystyle { tbinom {c_ {i}} {i}} = 0}$ , jmenovitě C_i = i − 1. Tak jsme našli 5-kombinaci {8, 6, 3, 1, 0}.

Příklad národní loterie v aplikaci Excel

Pro každou z ${ displaystyle { binom {49} {6}}}$ loterijní kombinace C₁ < C₂ < C₃ < C₄ < C₅ < C₆ , existuje číslo seznamu N mezi 0 a ${ displaystyle { binom {49} {6}} - 1}$ který lze najít přidáním

{ displaystyle { binom {49-c_ {1}} {6}} + { binom {49-c_ {2}} {5}} + { binom {49-c_ {3}} {4}} + { binom {49-c_ {4}} {3}} + { binom {49-c_ {5}} {2}} + { binom {49-c_ {6}} {1}}.}

Předpokládejme, že chcete v seznamu možných výsledků najít pozici výsledku Britské národní loterie 3,6,15,17,18,35. Funkce Excel KOMBINOVAT (49,6) by ukázala, že počet výsledků je 13983816. Nyní, když do buňky vložíte čísla 3,6,15,17,18,35 a vzorce COMBIN (49-3,6), COMBIN ( 49-6,5), COMBIN (49-15,4), COMBIN (49-17,3), COMBIN (49-18,2), 49-35 pod každou z nich. Místo skutečných hodnot použijte odkazy na buňky, skutečné hodnoty jsou uvedeny kvůli čitelnosti. Získáte řadu čísel 9366819,962598,46376,4960,465,14. Jejich přidáním by se zobrazila konkrétní pozice 10381232. Všimněte si, že pro získání 14 nepotřebujete použít vzorec KOMBINOVÁNÍ (49-35,1). Můžete jej mít odečtením samotného 49-35. Funkce COMBIN také nevrací hodnotu 0 v případě, že hodnota 49-X bude menší než 6. K převodu # ČÍSLO budete muset použít funkci IF s funkcí ISNUMBER! do 0.

Nyní je zpětné inženýrství trochu složitější. Můžete použít 49 příkazů IF v jedné buňce nebo použít řešič k nalezení maximálního argumentu, aby výsledek KOMBINACE byl menší nebo roven číslu pozice. Místo toho použijeme tabulku 6 x 49 a použijme funkci MATCH, kde výsledným číslem řádku bude argument a číslo koule. Pokud vytvoříte záhlaví sloupců od 6 do 1 (B1: G1) v sestupném pořadí a popisky řádků od 1 do 49 (A2: A50) ve vzestupném pořadí (svisle vzestupně v aplikaci Excel znamená, že čísla rostou shora dolů). Pak pokud vyplníte tabulku vzorcem KOMBINOVAT ($ A2, B $ 1) počínaje od levého horního rohu. Znaky $ zajistí, že hodnoty indexu budou vždy převzaty z řádku záhlaví a sloupce štítku. Vyměnit # ČÍSLO! s nulami. Měli byste dostat něco takového:

	6	5	4	3	2	11	0	0	0	0	0	12	0	0	0	0	1	23	0	0	0	1	3	34	0	0	1	4	6	45	0	1	5	10	10	56	1	6	15	20	15	67	7	21	35	35	21	78	28	56	70	56	28	89	84	126	126	84	36	910	210	252	210	120	45	1011	462	462	330	165	55	1112	924	792	495	220	66	12...49	13983816	1906884	211876	18424	1176	49

Nyní, pokud vytvoříte nový řádek šesti buněk a naplníte je vzorci, které by v každém sloupci nalezly největší hodnoty, které jsou menší nebo rovny danému číslu pozice: První buňka s = INDEX (B2: B50, MATCH (10381232) , B2: B50)), zbytek buněk s

INDEX (C2: C50, MATCH (10381232-SUM (z předchozích buněk), C2: C50)) ... INDEX (G2: G50, MATCH (10381232-SUM (z předchozích buněk), G2: G50))

To by vám představilo řadu hodnot, které jste již viděli 9366819,962598,46376,4960,465,14 Nyní v další řadě první buňka napište = 49-MATCH (10381232, B2: B50) a podobně

= 49-MATCH (10381232-9366819, C2: C50) ... = 49-MATCH (10381232-9366819-962598-46376-4960-465, G2: G50)

Opět použijte odkazy na buňky namísto skutečných hodnot. Měli byste dostat originální čísla míčů 3,6,15,17,18,35.

Nyní můžete vygenerovat novou kombinaci čísel loterií z single = randb Between (1, combine (49,6)) nebo se můžete podívat na čísla pozic seznamu dřívějších výsledků a zjistit, zda existuje trend.

Aplikace

Dalo by se použít kombinatorický číselný systém k vypsání nebo procházení všech k-kombinace dané konečné množiny, ale toto je velmi neefektivní způsob. Opravdu, vzhledem k některým k-kombinace je mnohem jednodušší najít další kombinaci v lexikografickém řazení přímo než převést číslo na k-kombinace metodou uvedenou výše. Chcete-li najít další kombinaci, najděte tu nejmenší i ≥ 2 pro které C_i ≥ C_{i − 1}+2 (pokud takové neexistují i, vzít i = k+1); pak zvýšit C_i−1 jeden a nastavit vše C_j s j < i − 1 na jejich minimální hodnotu j − 1. Pokud k-kombinaci představuje jeho charakteristický vektor, to je jako binární hodnota s k bity 1, pak lze další takovou hodnotu vypočítat bez jakékoli smyčky pomocí bitové aritmetiky: následující C ++ funkce bude postupovat X na tuto hodnotu nebo návrat Nepravdivé:

// najít další k-kombinacibool next_combination(nepodepsaný dlouho& X) // předpokládejme, že x má v binárním tvaru x'01 ^ a10 ^ b{  nepodepsaný dlouho u = X & -X; // extrahovat bit zcela vpravo 1; u = 0'00 ^ a10 ^ b  nepodepsaný dlouho proti = u + X; // nastavit poslední nekoncový bit 0 a vymazat doprava; v = x'10 ^ a00 ^ b  -li (proti==0) // poté přeteče ve v nebo x == 0    vrátit se Nepravdivé; // signál, že další k-kombinaci nelze reprezentovat  X = proti +(((proti^X)/u)>>2); // v ^ x = 0'11 ^ a10 ^ b, (v ^ x) / u = 0'0 ^ b1 ^ {a + 2} a x ← x'100 ^ b1 ^ a  vrátit se skutečný; // úspěšné dokončení}

Tomu se říká Gosper hack;^[7]odpovídající montážní kód byl popsán jako položka 175 v HAKMEM.

Na druhou stranu možnost přímo generovat k-kombinace na indexu N má užitečné aplikace. Zejména umožňuje generování náhodných k-kombinace an n-prvková sada pomocí náhodného celého čísla N s ${ displaystyle 0 leq N <{ tbinom {n} {k}}}$ jednoduše převedením tohoto čísla na odpovídající k-kombinace. Pokud počítačový program potřebuje udržovat tabulku s informacemi o každém k-kombinace dané konečné množiny, výpočet indexu N spojené s kombinací umožní přístup k tabulce bez vyhledávání.

Viz také

Faktoriální číselný systém (nazývané také factoradics)
Systém počátečních čísel

Reference

^ Aplikovaná kombinatorická matematika, Ed. E. F. Beckenbach (1964), str. 27–30.
^ http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf
^ https://www.sagemath.org/doc/reference/sage/combinat/subset.html
^ Knuth, D. E. (2005), „Generování všech kombinací a oddílů“, Umění počítačového programování, 4, Fascicle 3, Addison-Wesley, str. 5-6, ISBN 0-201-85394-9.
^ Pascal, Ernesto (1887), Giornale di Matematiche, 25, str. 45−49
^ McCaffrey, James (2004), Generování m. Lexikografického prvku matematické kombinace, Microsoft Developer Network
^ Knuth, D. E. (2009), „Bitové triky a techniky“, Umění počítačového programování, 4, Fascicle 1, Addison-Wesley, str. 54, ISBN 0-321-58050-8

[1] Aplikovaná kombinatorická matematika, Ed. E. F. Beckenbach (1964), str. 27–30.

[2] ttp://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf

[3] ttps://www.sagemath.org/doc/reference/sage/combinat/subset.html

[4] Knuth, D. E. (2005), „Generování všech kombinací a oddílů“, Umění počítačového programování, 4, Fascicle 3, Addison-Wesley, str. 5-6, ISBN 0-201-85394-9.

[5] Pascal, Ernesto (1887), Giornale di Matematiche, 25, str. 45−49

[6] McCaffrey, James (2004), Generování m. Lexikografického prvku matematické kombinace, Microsoft Developer Network

[7] Knuth, D. E. (2009), „Bitové triky a techniky“, Umění počítačového programování, 4, Fascicle 1, Addison-Wesley, str. 54, ISBN 0-321-58050-8

[1]

[2]

[3]

[4]

[5]

[6]

[7]