We're a community of 1077K IT Pros here for help, advice, solutions, professional growth and fun. Join us!
1,076,240 Members — Technology Publication meets Social Media

# Permutations with recursive generator

By Tony Veijalainen on Jun 27th, 2012 1:42 am

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
"""``````
Post: Markdown Syntax: Formatting Help

You
View similar articles that have also been tagged:

© 2013 DaniWeb® LLC
Page rendered in 0.0521 seconds using 2.65MB