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.
""" 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
"""We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.