simple recursion help

[Alex Martelli]

Stephen Waterbury <golux at comcast.net> wrote:

> Hung Jung Lu wrote:
> > ...  The functional version would be:
> > 
> > strings = lambda Xs, k: reduce(lambda r, i: [p + x for p in r for x
> > in Xs], range(k), [''])
> 
> Wow!  Grand prize for elegance.  :)

And almost for performance -- it's an order of magnitude faster than
other ones I've timed.  Of course, as usual, you can get another 10% or
so if you avoid reduce and lambda, implementing exactly the same
algorithm as:

def stringo(Xs, k):
    r = ['']
    for i in range(k):
        r = [p+x for p in r for x in Xs]
    return r

$ python -m timeit -s'import ov' 'ov.strings("abc",3)'
10000 loops, best of 3: 144 usec per loop
$ python -m timeit -s'import ov' 'ov.strings("abc",3)'
10000 loops, best of 3: 142 usec per loop

$ python -m timeit -s'import ov' 'ov.stringo("abc",3)'
10000 loops, best of 3: 126 usec per loop
$ python -m timeit -s'import ov' 'ov.stringo("abc",3)'
10000 loops, best of 3: 125 usec per loop


Alex