Az iskolai matematikából is ismert a Pascal háromszög. Azt, hogy ez mi, több megközelítési móddal is le lehet írni. Többek között úgy is meghatározható, hogy olyan egymást követő sorozatok elemeiből áll, amelyek 1-gyel kezdődnek és 1-gyel végződnek, a többi elem pedig az előző sorozatból származtatható olyan módon, hogy egy k indexű elem az előző sor k-1 és k indexű elemeinek összege. Így, minden egyes sor az előző sornál eggyel hosszabb. A Pascal háromszög alapvető jellemzői az ábra mutatja.
Ennek alapján azt is lehet mondani, hogy a Pascal háromszög a binomiális együtthatók háromszög alakban történő elrendezése. A binomiális együtthatók értéke pedig „n alatt a k”, azaz egy n elemű halmaz k elemű részhalmazainak a száma, vagy kombinatorikai szóhasználattal: a kombinációk számát adja meg, vagyis azt, hogy hányféleképpen választható ki k elem n különböző elem közül.
Bár a Pascal háromszögnek elsősorban elméleti a jelentősége, de a kombinációk számítása kapcsán olykor jól jöhet. A Python 3.8 verziójától a math modulban rendelkezésre áll a comb(n, k) függvény, amivel könnyen számolhatunk kombinációt. Az ennél korábbi Python verziók esetén a kombinációk számát faktoriálisakkal lehet ugyan számolni az n!/(n-k)!/k! képlettel, de ez egyrészt float eredményt ad, ami nem mindig megfelelő és így extra típuskonverziót igényelhet, másrészt a float típusnál elkerülhetetlen számítási pontatlanság is felléphet, ami például összehasonlításoknál jelenthet gondot /ha int típus lenne az eredmény ilyen gond nem lépne fel/. Erre láthatunk példát alább.
|
1 2 3 4 5 6 7 |
from math import comb, factorial n, k = 200, 50 komb1 = comb(n, k) komb2 = factorial(n) / factorial(n - k) / factorial(k) print(komb1 / komb2) # Eredmény: 0.9999999999999998 |
Ha tehát int eredményt szeretnénk és nincs comb() függvény, akkor megoldási eszközként használhatjuk a Pascal háromszöget. Továbbá akkor is bevethetjük, ha ismerjük a kombinációk számát, valamint az n vagy k értékét, és keressük a fennmaradó ismeretlent.
Ahhoz, hogy alkalmazni tudjuk a Pascal háromszöget, készíteni kell egy olyan függvényt, amely annak n. sorát adja ki. Alább több megvalósítási változatot mutatunk aszerint, hogy a függvénytörzsben rekurziót vagy ciklust alkalmazunk, vagy generátorfüggvényt készítünk. A Pascal háromszög fent megadott definícióját követik a kódsorok, így különösebb magyarázatra nem szorulnak. A rekurziós megoldásban egy memoizált változatot is mutatunk.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
# ------------------- Pascal háromszög sorait előállító függvények ----------------------------- # Rekurzióval def pascal_sor1(n): if n == 0: return [1] psor = pascal_sor1(n - 1) return [1] + [psor[i] + psor[i + 1] for i in range(0, n - 1)] + [1] # Memoizált rekurzióval def pascal_sor2(n, sorok={0: [1]}): if n in sorok: return sorok[n] psor = [1, *[pascal_sor2(n - 1, sorok)[i] + pascal_sor2(n - 1, sorok)[i + 1] for i in range(0, n - 1)], 1] sorok[n] = psor return psor # Ciklussal def pascal_sor3(n): előző_sor = [1] aktuális_sor = előző_sor for si in range(n): aktuális_sor = [1] + [előző_sor[i] + előző_sor[i + 1] for i in range(len(előző_sor) - 1)] + [1] előző_sor = aktuális_sor return aktuális_sor # Generátorfüggvénnyel def pascal_sor4(): előző_sor = [1] yield előző_sor while True: aktuális_sor = [1] + [előző_sor[i] + előző_sor[i + 1] for i in range(len(előző_sor) - 1)] + [1] előző_sor = aktuális_sor yield aktuális_sor |
A függvényeket a fentebb említett alkalmazási esetekre teszteltük, amiket alább követhetünk nyomon.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
# TESZT # Kombináció számítás: 5-ös lottó szelvények száma a biztos telitalálathoz. print('A biztos 5-ös találathoz a szelvények száma:', pascal_sor2(90)[5]) # Eredmény: A biztos 5-ös találathoz a szelvények száma: 43949268 # Kérdés: n számból mennyi 10-nél kisebbet kellene legfeljebb választani, hogy # legfeljebb b darab legyen a kombinációk száma? n = 90 b = 44_000_000 # Előállítjuk a Pascal háromszög n. sorát, és végighaladunk annak elemein. # Egy listát építünk fel azon elemek indexeiből, amelyekre teljesül, hogy az # elemérték kisebb, mint a megadott b szám, és az index egyjegyű szám. # A triviális elemértékeket (1, n) nem vesszük figyelembe. kiválasztások_száma = [k for k, komb in enumerate(pascal_sor3(n)) if komb <= b and komb not in [1, n] if k < 10] print(f'{n} számból legfeljebb {max(kiválasztások_száma)} számot kell ' f'választani, hogy legfeljebb {b:,} legyen a kombinációk száma.') # Eredmény: # 90 számból legfeljebb 5 számot kell választani, hogy legfeljebb 44,000,000 legyen a kombinációk száma. # Kérdés: Legalább hány számból kell kiválasztani k-t, hogy ahhoz, hogy a kombinációk száma ne legyen kisebb mint b? k = 6 b = 8_000_000 for n, psor in enumerate(pascal_sor4()): # Generáljuk az egyes Pascal háromszög sorokat és csak az érdekel, amely legalább k hosszú. # Ha ez megvan és ennek k. eleme nagyobb, mint a megadott b érték, akkor megtaláltuk, amit kerestünk és kiírjuk. if len(psor) > k and psor[k] >= b: print(f'Legalább {n} számból kell {k} számot kiválasztani, hogy ' f'a kombinációk száma ne legyen kisebb mint {b:,}.') break # Eredmény: # Legalább 45 számból kell 6 számot kiválasztani, hogy a kombinációk száma ne legyen kisebb mint 8,000,000. |
Ehhez a témához, illetve a mintakódokhoz kapcsolódóan a Python tudásépítés lépésről lépésre című e-könyvben a a math modul mellett a rekurzív és generátorfüggvények létrehozásáról, valamint a memoizációról, illetve a listaépítőkről, a listák összefűzéséről és elemeik kicsomagolásáról szóló részeket érdemes feleleveníteni vagy tanulmányozni.