Python: using a recursive algorithm as a generator

def getPermutations(string, prefix=""):    if len(string) == 1:        yield prefix + string    else:        for i in xrange(len(string)):            for perm in getPermutations(string[:i] + string[i+1:], prefix+string[i]):                yield perm

Or without an accumulator:

def getPermutations(string):    if len(string) == 1:        yield string    else:        for i in xrange(len(string)):            for perm in getPermutations(string[:i] + string[i+1:]):                yield string[i] + perm

This avoids the len(string)-deep recursion, and is in general a nice way to handle generators-inside-generators:

from types import GeneratorTypedef flatten(*stack):    stack = list(stack)    while stack:        try: x = stack[0].next()        except StopIteration:            stack.pop(0)            continue        if isinstance(x, GeneratorType): stack.insert(0, x)        else: yield xdef _getPermutations(string, prefix=""):    if len(string) == 1: yield prefix + string    else: yield (_getPermutations(string[:i]+string[i+1:], prefix+string[i])            for i in range(len(string)))def getPermutations(string): return flatten(_getPermutations(string))for permutation in getPermutations("abcd"): print permutation

flatten allows us to continue progress in another generator by simply yielding it, instead of iterating through it and yielding each item manually.

Python 3.3 will add yield from to the syntax, which allows for natural delegation to a sub-generator:

def getPermutations(string, prefix=""):    if len(string) == 1:        yield prefix + string    else:        for i in range(len(string)):            yield from getPermutations(string[:i]+string[i+1:], prefix+string[i])

The interior call to getPermutations -- it's a generator, too.

def getPermutations(string, prefix=""):   if len(string) == 1:      yield prefix + string               else:      for i in range(len(string)):         getPermutations(string[:i]+string[i+1:], prefix+string[i])  # <-----

You need to iterate through that with a for-loop (see @MizardX posting, which edged me out by seconds!)