Menu
Recently I wrote a function to generate certain sequences with nontrivial constraints. The problem came with a natural recursive solution. Now it happens that, even for relatively small input, the sequences are several thousands, thus I would prefer to use my algorithm as a generator instead of using it to fill a list with all the sequences.
Here is an example. Suppose we want to compute all the permutations of a string with a recursive function. The following naive algorithm takes an extra argument 'storage' and appends a permutation to it whenever it finds one:
def getPermutations(string, storage, prefix=""): if len(string) == 1: storage.append(prefix + string) # <----- else: for i in range(len(string)): getPermutations(string[:i]+string[i+1:], storage, prefix+string[i]) storage = [] getPermutations("abcd", storage) for permutation in storage: print permutation (Please don't care about inefficiency, this is only an example.)
Now I want to turn my function into a generator, i.e. to yield a permutation instead of appending it to the storage list:
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]) for permutation in getPermutations("abcd"): print permutation This code does not work (the function behaves like an empty generator).
Am I missing something? Is there a way to turn the above recursive algorithm into a generator without replacing it with an iterative one?
707
The important thing to note in this example is: the generator function recursively calls itself in a for loop, which sees an iterator and automatically uses the iteration protocol on it, so it actually gets values from it.
It is fairly simple to create a generator in Python. It is as easy as defining a normal function, but with a yield statement instead of a return statement. If a function contains at least one yield statement (it may contain other yield or return statements), it becomes a generator function.
In short, recursion is not bad in Python and is often needed for programs that will be doing depth first traversals like web crawlers or directory searches. The Towers of Hanoi smallest steps problem can also be solved using a recursive algorithm with the following Python code.
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 GeneratorType def 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 x def _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]) If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
