Here you see how one could use recursion together with generators for (inefficient) permutations generator. It is kind of interesting to know how one can do it recursively (of course there exist many ways).

Anyway this snippet demonstrates how you can use recursive generator call to feed a for statement. If you want usefull use of recursive generator, see my 11.11.11 11:11:11 Code Snippet post of full multiword anagram program.

139 Views
``````""" Demonstrate recursion by recursive algorithm of
insertion to shorter permutations, using of generators,
function returning tuple result to clean up code for halfing list

"""

import pretty # http://www.daniweb.com/software-development/python/code/345935/printing-things-nicely-pretty-printer-revisited

def halfs(s):
""" helper for cleaner dividing of list in halfs,
starting from end to give more natural order"""
for i in reversed(range(len(s)+1)):
yield s[:i], s[i:]

def permutations(vals):
""" Do recursive permutations
by inserting first value to all permutations of all but first tail

"""
# make sure iterable has length by making it list
vals = list(vals)
if len(vals) <= 1:
yield vals
else:
this = [vals[-1]]
for permute in permutations(vals[:-1]):
for start, end in halfs(permute):
yield start + this + end

if __name__ == '__main__':
pretty.printer(list(permutations(range(4))))

print('''
Timing performance with iterative version
by generating 10! permutations of 10 elements''')

import time
t0 = time.clock()
print(sum(1 for p in permutations(range(10))))
print('%f s by recursion' % (time.clock()-t0))

from itertools import permutations as p
t0 = time.clock()
print(sum(1 for p in p(range(10))))
print('%f s by iteration' % (time.clock()-t0))

""" Output:

[
[0, 1, 2, 3],
[0, 1, 3, 2],
[0, 3, 1, 2],
[3, 0, 1, 2],
[0, 2, 1, 3],
[0, 2, 3, 1],
[0, 3, 2, 1],
[3, 0, 2, 1],
[2, 0, 1, 3],
[2, 0, 3, 1],
[2, 3, 0, 1],
[3, 2, 0, 1],
[1, 0, 2, 3],
[1, 0, 3, 2],
[1, 3, 0, 2],
[3, 1, 0, 2],
[1, 2, 0, 3],
[1, 2, 3, 0],
[1, 3, 2, 0],
[3, 1, 2, 0],
[2, 1, 0, 3],
[2, 1, 3, 0],
[2, 3, 1, 0],
[3, 2, 1, 0]]

Timing performance with iterative version
by generating 10! permutations of 10 elements
3628800
11.746256 s by recursion
3628800
1.476485 s by iteration
"""``````
About the Author

IT Pro doing Eng-Fin-Eng translations