Ö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ⁿ. 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}