Combinations and recursion, from an ASPN snippet

[Steven Taschuk]

Quoth dromedary:
 [...]
> I'm still rather green with recursion. I understand it in principle,
> but I'm not quite following what happens, say, here:
> 
>       printUniqueCombinations(alist[i+1:], numb-1, blist)
>       blist.pop()
> 
> For example, when numb gets to 1, the 
> 
>    if not numb:
> 
> kicks in. But the recursive loop is still running (on its second
> iteration?), so to me it looks as it the next printCombinations() call
> gets fed a 0 for numb, making the numb -1 a negative 1. Is that what
> finally breaks that loop and allows the next line, the blist.pop(), to
> run? Wouldn't the function just accept a negative number?

In fact there is no call to printUniqueCombinations with -1; numb
never gets updated.  To see this, first use these line numbers:

    0 def printUniqueCombinations(alist, numb, blist=[]):
    1    if not numb: 
    2       return printList(blist)
    3    for i in range(len(alist)):
    4       blist.append(alist[i])
    5       printUniqueCombinations(alist[i+1:], numb-1, blist)
    6       blist.pop()

Now, the call
    printUniqueCombinations(list('love'), 2)
causes this sequence of events:

    (0) # called with alist = 'love', numb = 2, blist = []
    (1) if not numb: # false; numb == 2
    (3) for i in range(4):
            # iteration with i = 0
    (4)     blist.append('l') # blist is now ['l']
    (5)     printUniqueCombinations('ove', 1, blist) # recursion!
            (0) # called with alist = 'ove', numb = 1, blist = ['l']
            (1) if not numb: # false; numb == 1
            (3) for i in range(3):
                    # iteration with i = 0
            (4)     blist.append('o') # blist is now ['l', 'o']
            (5)     printUniqueCombinations('ve', 0, blist) # recursion!
                    (0) # called with alist = 've', numb = 0, blist = ['l','o']
                    (1) if not numb: # true! numb == 0
                    (2)     return printList(blist) # prints 'lo' and returns
            (6)     blist.pop() # blist is now ['l']
                    # iteration with i = 1
            (4)     blist.append('v') # blist is now ['l', 'v']
            (5)     printUniqueCombinations('e', 0, blist) # recursion!
                    (0) # called with alist = 'e', numb = 0, blist = ['l','v']
                    (1) if not numb: # true! numb == 0
                    (2)     return printList(blist) # prints 'lv' and returns
            (6)     blist.pop() # blist is now ['l']
                    # iteration with i = 2
            (4)     blist.append('e') # blist is now ['l', 'e']
            (5)     printUniqueCombinations('', 0, blist) # recursion!
                    (0) # called with alist = '', numb = 0, blist = ['l','e']
                    (1) if not numb: # true! numb == 0
                    (2)     return printList(blist) # prints 'le' and returns

... and so forth.  Not especially that the value of numb one level
down in the recursion does not affect the value of numb in the
current level.

> (BTW, is the printCombinations() function above for combinations or
> permutations? I'd have thought it was the latter.)

Combinations.  (But it does give each permutation of a combination
unique status.)

-- 
Steven Taschuk                  staschuk at telusplanet.net
"Telekinesis would be worth patenting."  -- James Gleick