Lássunk végül egy halmazokkal kapcsolatos alapfeladatot: határozzuk meg az n-elemű halmaz összes részhalmazainak számát, illetve soroljuk fel azokat.
A számeredmény ezúttal 2n. Ez nem ok nélkül emlékeztet az előző szakaszban látottra, ahogyan a két algoritmus sem véletlenül hasonlít egymásra…
Első megközelítésben idézzük föl a részhalmazok számára vonatkozó kijelentés egy lehetséges igazolásának alapgondolatát: minden elem alá odaírhatjuk, hogy az egy adott részhalmaznak is eleme lesz-e – ennek megfelelően a részhalmazok helyett elegendő az n hosszúságú i/n-sorozatokat felsorolnunk.
def subs(k, n, sset): if k<n: subs(k+1, n, sset+'i') subs(k+1, n, sset+'n') elif k==n: print(sset, end=' ') subs(0, 4, '') print()
A fenti program kimenete négyelemű halmaz kapcsán:
iiii iiin iini iinn inii inin inni innn niii niin nini ninn nnii nnin nnni nnnn
Ha a cél a részhalmazok felsorolása, akkor is megegyezik az algoritmusok alapgondolata. A kiindulási halmaz elemeit ezúttal tároljuk egy listában, de a részhalmazokat adjuk meg a python halmaztípusával.
def subt(k, n, set, sset): if k<n: subt(k+1, n, set, sset) subt(k+1, n, set, sset | {set[k]}) elif k==n: print(sset, end=' ') subt(0, 4, [0, 1, 2, 3], set()) print()
A halmaztípus jellegzetességének megfelelően a kimenettől nem várhatunk semmiféle rendezettséget. Emlékezzünk vissza arra is, hogy az üres halmazt set() adja meg ({} az üres szótárt jelöli).
set() {3} {2} {2, 3} {1} {1, 3} {1, 2} {1, 2, 3} {0} {0, 3} {0, 2} {0, 2, 3} {0, 1} {0, 1, 3} {0, 1, 2} {0, 1, 2, 3}