```
""" 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

1

Contributor0

Replies2

Views**Are you able to help answer this sponsored question?**

Questions asked by members who have earned a lot of community kudos are featured in order to give back and encourage quality replies.

Recommended Topics