Permutations Generator vs Return Function

Question

So here are my two functions that return all the permutations of a string.

def permutations(sequence):
    if len(sequence) <= 1:
        return [sequence]        
    else:
        l = []
        perms = permutations(sequence[1:])
        for perm in perms:
            for index in xrange(len(perm)+1):
                l.append(perm[:index]+sequence[0]+perm[index:])
        return l

and

def permutations_gen(sequence):
    if len(sequence) <= 1:
        yield sequence
    else:
        for perm in permutations_gen(sequence[1:]):
            for index in xrange(len(perm)+1):
                yield perm[:index] + sequence[0] + perm[index:]

It seems to me that the second one - the generator - should be faster than the first, especially when running it with large strings. After all, a string of length 11 has 39916800 permutations, and it seems like, because the first function stores so many lists in memory, the generator would be much faster.

But when I time these two, the first one is almost always faster, but they are very close. Why isn't the generator faster?

Also, I have been trying to think of a way to generate permutations iteratively, without the recursive call, but cannot think of a way. How would I go about this?

Using less memory doesn't necessarily make it faster - the lighter footprint is a benefit in itself. — jonrsharpe, May 08 '16 at 18:42
@jonrsharpe not only "doesnt necessarily", but most of the time actually causes code to run slower ... its a trade off of space vs time — Joran Beasley, May 08 '16 at 18:54
For iterative algorithms, see e.g. http://stackoverflow.com/questions/34013675/permutations-without-recursive-function-call — m69's been on strike for years, May 08 '16 at 19:02

Permutations Generator vs Return Function

0 Answers0