This example uses an algorithm to find a number's prime factors. For other interesting algorithms, see my book Essential Algorithms, Second Edition. The book describes many fascinating algorithms in pseudocode with source code available for download in Python and C#.

Title: Use the yield statement to recursively generate permutations of values in Python

The post Recursively generate permutations of values in Python shows how you can generate permutations of values. (The itertools library has a permutations method that can do this more easily. See that post for details.)

The yield statement lets you make a generator that produces a sequence of values that you can later loop through. One nice feature of yield is that your generator function only produces values ae they are needed. In general that means your code isn't stopped waiting while you generate every value that you may eventually need.

A particularly handy use for values generated by yield is that it lets your program perform other actions between generating the values. For example, the program might display some output and then use after to wait a bit before processing the next value. I'll post an example that does that shortly. This example focuses on using yield to generate values recursively. That requires one special technique: the recursive method must iterate through the values returned by its recursive call and yield them separately so they can move up the call stack.

That's the basic idea. Let's get to the details!

See the post Recursively generate permutations of values in Python to see how the recursive method works. The following code shows the new version of the generate_permutations.

def generate_permutations(values, is_used, current_permutation): if len(current_permutation) == len(values): yield current_permutation else: for i in range(len(values)): if not is_used[i]: current_permutation.append(values[i]) is_used[i] = True # Recursively expand out the current permutation. # The recursive call is itself a generator so # loop through its results and yield them. for permutation in generate_permutations( values, is_used, current_permutation): yield permutation current_permutation.pop() is_used[i] = False

The method first checks the length of the current permutation. If it's a complete permutation, the method uses yield to return it.

If the permutation is not full, the method loops through the values as in the previous version. If a value is unused, the method adds it to the current permutation, recursively calls itself, and then removes the value from the current permutation as before. The big difference is that this version loops through the values yielded by the recursive call and yields them.

The following code shows how the main program calls the method.

values = ['Ant', 'Bat', 'Cat'] is_used = [False for _ in values] current_permutation = [] for permutation in generate_permutations(values, is_used, current_permutation): print(permutation)

That's all there is to it. It's not a huge improvement over the previous version if you just want to iterate over all of the values. This version would let you stop early if you only want to generate some of the values. The itertools permutations method also would let you do that.

This version would let you do other things like only generate permutations where adjacent items have a particular relationship. For example, if you want odd-numbered entries to be larger than even-numbered ones. That would be weird, but you could do it.

In my next post, I'll show how you can use this technique to display graphical results and pause before displaying the next one.

Download the example to see additional details.