Combinations and recursion, from an ASPN snippet

dromedary camel at oasis.com
Tue Mar 18 22:12:54 EST 2003


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




More information about the Python-list mailing list