Permutations with recursive generator

0

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

Ad: Wells Fargo Advisors Estate Planning Kit

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