Kako naredimo potenčno množico

Napišimo funkcijo potencna(s), ki za podani seznam elementov s vrne seznam vseh njegovih podseznamov. potencna([1, 2, 3]) mora vrniti [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]. Vrstni red ni pomemben. Namesto s seznami bi lahko delali z množicami, vendar ne bomo, ker je s seznami lažje; tako ali tako bomo imeli dovolj drugih težav.

Ne preveč lepa rekurzija: nabiranje

Najprej rešimo enostavnejšo nalogo: izpišimo vse podsezname. Funkcija bo imela dva argumenta: seznam s in še vrečo (vreca), v katero bomo nabirali elemente. - Najprej sestavimo vse podmnožice s[1:] (torej s brez prvega elementa), ki vsebujejo s[0]: pokličemo potencna(s[1:], vreca + [s[0]]), s čimer vržemo s[0] v vrečo (k tistemu, kar se je morda že nabralo v njej) in prepustimo rekurzivnemu klicu, da vanjo doda - ali pa ne - še kaj od preostalih elementov. - Nato sestavimo še podmnožice s[1:], ki ne vsebujejo s[0]: pokličemo potencna(s[1:], vreca), tako da se bo v vreči morda nabralo kaj iz s[1:], s[0] pa ne.

Ko je s prazen, se je rekurzija iztekla in le še izpišemo, kar je v vreči.

def potencna(s, vreca):
    if not s:
        print(vreca)
    else:
        potencna(s[1:], vreca + [s[0]])
        potencna(s[1:], vreca)

Funkcijo pokličemo z, recimo potencna([1, 2, 3, 4, 5], []), da se prepričamo, da deluje.

Zdaj pa predelajmo funkcijo tako, da bo vrnila seznam seznamov, namesto da jih izpisuje.

• Če je s prazen, mora očitno vrniti vreco.

• Sicer pa pokliče potencna(s[1:], vreca) in potencna(s[1:], vreca + [s[0]]). Tako dobi seznam vseh podmnožic brez s[0] in z s[0]. Sešteje in vrne.

  def potencna(s, vreca): if not s: return [vreca] else: return potencna(s[1:], vreca) + potencna(s[1:], vreca + [s[0]])

Pokličemo print(potencna([1, 2, 3, 4, 5], [])) in vidimo, da deluje.

Lepa rekurzija

No, tako, kot smo naredili zgoraj, se ne dela. Razen, kadar imamo za to kak razlog. Bil sem v dvomih, ali naj to sploh pokažem, vendar sem, ker se velikokrat ujamemo v takšnem načinu razmišljanja, zato le pokažimo, kako napačen je in kako preprosteje gre.

Problem gornjega razmišljanja je, da razmišljamo naprej namesto nazaj. Vzeli smo prvi element, naredili odločitev v zvezi z njim in mu potem pridružili potenčno množico ostanka. Rekurzijo je boljše načrtovati v drugo smer. Najprej rešimo preprostejši problem (potenčna množica seznama brez prvega elementa), nato pa rešitev razširimo v rešitev, ki upošteva tudi ta, prvi element.

Problem je očitno najpreprostejši, če je seznam s prazen. V tem primeru potenčna množica vsebuje eno samo množico, namreč prazno množico.

if not s:
    return [[]]

Sicer pa naredimo tole: najprej sestavimo potenčno množico s-ja brez prvega elementa, brez = potencna(s[1:]). Dobili smo ... pač nekaj množic. Zdaj ta seznam podvojimo: enkrat ga vzamemo takšnega kot je (brez), enkrat pa k vsem njegovim elementom dodamo še s[0] ([[s[0]] + b for b in brez]). To potem vrnemo.

def potencna(s):
    if not s:
        return [[]]
    else:
        brez = potencna(s[1:])
        return brez + [[s[0]] + b for b in brez]

Ta rešitev je obrnjena v pravo smer in zato precej krajša in brez dodatnega argumenta, vreče. Poleg tega pa ima še eno lepo lastnost. "Grda" različica dvakrat pokliče sama sebe. Za potenčno množico n elementov se pokliče 2ⁿ-krat. Ta, druga, se pokliče le enkrat. Za potenčno množico petih elementov se pokliče n-krat.

To sicer ne pomeni (nujno), da je hitrejša: prva različica vsebuje le eno seštevanje, druga pa zanko. Na koncu koncev morata obe sestaviti množico, ki vsebuje 2ⁿ elementov, kar bo moralo zahtevati 2ⁿ korakov. No, v praksi bo druga hitrejša zato, ker so rekurzivni klici počasnejši od zanke.

A hitrost še niti ni tako pomembna: kar tule šteje, je eleganca. :)