Combinations and recursion, from an ASPN snippet

[Andy Jewell]

On Wednesday 19 Mar 2003 3:12 am, dromedary wrote:
> A short Python program for combinations on ASPN contains this code (I
> snipped out the argv[] stuff):
>
> import sys
>
> def printList(alist):
>    print ''.join(alist)
>
> def printUniqueCombinations(alist, numb, blist=[]):
>    if not numb:
>       return printList(blist)
>    for i in range(len(alist)):
>       blist.append(alist[i])
>       printUniqueCombinations(alist[i+1:], numb-1, blist)
>       blist.pop()
>
> def printCombinations(alist, numb, blist=[]):
>    if not numb:
>       return printList(blist)
>    for i in range(len(alist)):
>       blist.append(alist.pop(i))
>       printCombinations(alist, numb-1, blist)
>       alist.insert(i, blist.pop())
>
> if __name__ == '__main__':
>    k='love'
>    n=2
>    print 'combinations of %d letters in "%s" ' % (n, k)
>    printCombinations(list(k), n)
>    print 'unique combinations of %d letters in "%s" ' % (n, k)
>    printUniqueCombinations(list(k), n)
>
>
> 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?
>
> Thanks for your help. I'd like to see if I can link the combination
> code to an anagram maker.
>
> (BTW, is the printCombinations() function above for combinations or
> permutations? I'd have thought it was the latter.)
>
> Jon

Recursion really hurt my head when I first came accross it, but it's such a 
powerful programming tool - recursive algorithms can be so much more elegant 
then iterative (well, sometimes, anyway).

There are a few things to always remember when writing recursive routines:

1) Always have a 'bail-out clause', a condition that when met, stops the 
recursion.

2) Don't forget that there is always a limit to the depth of recursion - 
Python has a (hard coded?) recursion limit, wheras other languages may be 
limited by factors such as stack size or memory availability, or both.

3) Local variables are local to the 'instance' of each call;  you need to use 
globals or parameters if you want to pass values between instances.  In this 
case the blist[] list is used.  Note the rules for default values are 
exploited here; lists are mutable types, and if you check the manual, you'll 
find that it says that default value parameters of mutable types are only 
evaluated once.  What this means is that if you change a mutable default 
parameter, it will STAY changed for subsequent calls (or recursions).  Hence 
the blist.pop(), to clear out unwanted members of the list!

I'm sure others will add more rules! :-)

I like to think of recursion as 'nesting' calls to the function, one inside 
the other:

1
  \
    2
      \
        3
          \
           4
             \
              :
             /
           4
          /
        3
      /
    2
   /
1

Bear in mind, though, that it won't usually be as 'tidy' as this!


IN MY OPINION the use of:

	if not numb:

could cause problems.  It will only work, as you've observed, when numb==0; if 
it goes -ve it will still evaluate to TRUE, i.e. non-zero.  If you change the 
code to accommodate a modification, that could break it.  You would get into 
an infinite recurse if you did:

	 printCombinations(list(k), -1)

Ok, well,  at least until numb wrapped to zero, but the recursion limit would 
come first, I'll warrant!

A better test would be:

	if a < 1:

The statement:

	return printList(blist)

will cause termination of the recursion because the *return* statement causes 
control to go back to the previous context.  As printList() does not 
(explicitly) return anything, it in fact returns None, so both the 
Combinations() functions will return None, eventually, but this value is not 
used (Python allows you to politely ignore return values).

To make the functions more usable for anagrams, you'd need to store up the 
combinations and probably return them as a list on termination.  That'd make 
a good exercise.

Hope this helps.  The best way to learn recursion is to play with it.  Use 
print statements liberally, and limit the recursion depth to a reasonable 
amount while you're at it - it's very hard to see what's going on when your 
program dumps 10 pages of output on the screen!

To further flex your new-found recursion muscle, try:

	Finding prime numbers
	Walking directory (or other) trees
	Simple fractals like Hilbert (say using the turtle module) 
	Towers of Hanoi problem
	Mandelbrot and Julia set fractals (hey, I can't help you there!)
	A forward-thinking, multiple strategy chess program 

Good luck!
-andyj