Gnezdenje klicev

Primer

Napiši funkcijo Kombinacije(t, k), ki kot parametra dobi tabelo t in naravno število k ter izpiše vse možne izbore k elementov tabele t. Primer: če je t = [10, 20, 30] in k = 2, moramo izpisati tri izbore: [10, 20], [10, 30] in [20, 30].

Začnimo kar pri prvem elementu tabele t: tega lahko vključimo v nek izbor ali pa ne. Če ga vključimo v izbor, moramo izbrati tudi k - 1 elementov iz preostanka tabele; če pa prvega elementa nismo vključili v izbor, moramo v nadaljevanju izbrati k elementov iz preostanka tabele.

V vsakem primeru torej pridemo do podproblema, ki je podobne oblike kot prvotni problem, le da se ne začne pri prvem elementu tabele, ampak šele pri drugem. Zato bomo lahko, če primerno napišemo funkcijo za generiranje vseh možnih izborov, ta podproblem reševali z isto funkcijo kot prvotni problem (glej program v nadaljevanju).

Vaja

(a) Preizkusi tu prikazano funkcijo Kombinacije še na večjem primeru (na primer na tabeli s 5 elementi in s k = 3).
(b) Na začetek in konec funkcije NastejIzbore dodaj stavke, ki izpišejo vrednosti parametrov, in z njihovo pomočjo opazuj, kako se gnezdijo klici funkcije in kaj se dogaja v njih.
(c) Spremeni funkciji tako, da izborov ne izpisujeta, pač pa vrneta število, ki pove, koliko je takih izborov.

def NastejIzbore(t, k, i, dosedanjiIzbor): # Parametri pomenijo: izbrati moramo še k # elementov tabele t z indeksov od i naprej. # Elementi, ki smo jih doslej že izbrali, pa # so v tabeli dosedanjiIzbor. # - Lahko da v tabeli ni dovolj elementov; # tedaj izbora ne bomo mogli končati. if i + k > len(t): return # - Ena možnost je, da zdaj v izbor vključimo # element t[i]. dosedanjiIzbor.append(t[i]) # - Če je k večji od 1, moramo zdaj izbrati še # drugih k-1 elementov iz preostanka tabele. if k > 1: NastejIzbore(t, k - 1, i + 1, dosedanjiIzbor) # - Sicer (pri k == 1) je izbor končan in ga # lahko izpišemo. else: print(dosedanjiIzbor) # - Pobrišimo element t[i] iz izbora. del dosedanjiIzbor[len(dosedanjiIzbor) - 1] # - Če elementa t[i] nimamo v izboru, moramo # zdaj izbrati še preostalih k elementov iz # preostanka tabele. NastejIzbore(t, k, i + 1, dosedanjiIzbor) def Kombinacije(t, k): NastejIzbore(t, k, 0, []) # Rešitev primera iz naloge Kombinacije([10, 20, 30], 2)

Izvedi Počisti