Tehetséggondozás az informatikában
Összes részhalmaz
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 2
n. 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}