CODEWITHSUNDEEP
python
Telek
Telek

Reputation: 47

Fastest permutations implementation in Python

I have the following implementation for permutation generation in python:

def perms(v):
    '''
    Generates permutations for sequence v
    :param v: sequence for permutations
    '''
    if not v:
        yield ()
    else:
        for p in perms(v[1:]):
            for i in range(len(v)):
                yield p[:i] + (v[0],) + p[i:]

It works faster than itertools.permutations (it also does less, I know). Is there a faster (or alternatively more compact) implementation. I tried implementing it with vector insert/delete and it seems slower.

Upvotes: 0

Views: 2501

Answers (1)

roman
roman

Reputation: 117380

>>> timeit.timeit("sum([1 for i in permutations([1, 2, 3, 4, 5])])", setup="from itertools import permutations", number=1000)
0.0829811965812155

>>> timeit.timeit("sum([1 for i in perms([1, 2, 3, 4, 5])])", setup="from test import perms", number=1000)
0.4672438746438843

it looks like your implementation is more than 5 times slower on this simple example. Am I missing something?

Upvotes: 3

Related Questions