CODEWITHSUNDEEP
pythonpython-2.7tuples
Barry
Barry

Reputation: 80

iterating from a tuple of tuples optimizations

Basic problem: take a list of digits, find all permutations, filter, filter again, and sum. this is my first python script so after some research i decided to use itertools.permutations. i then iterate through the tuple, and create a new tuple of tuples with only the tuples i wanted. i then concatenate the tuples because I want the permutations as numbers, not as broken strings. then i do one more filter and sum them together.

for 8 digits, this is taking me about 2.5 seconds, far too slow if i want to scale to 15 digits (my goal). (I decided to use tuples since a list of the permutations will be too large for memory)

EDIT: I realized that I don't care about the sum of the permutations, but rather just the count. If going the generator path, how could I include a counter instead of taking the sum? Updated my original code with [very] slight improvements shortcuts also, as to not just copy pasta suggested answers before I truly understand them.

import itertools

digits= [0,1,2,3,4,5,6,7]
digital=(itertools.permutations(digits))


mytuple=()
for i in digital:
    q=''
    j=list(i)
    if j[0] != 0:
        for k in range(len(j)):
            q=q+str(j[k])

        mytuple=mytuple+(q,)

#print mytuple

z = [i for i in mytuple if i%7==0]

print len(z)

this being my first python script, any non-optimization pointers would also be appreciated. thanks!

Upvotes: 1

Views: 120

Answers (3)

jez
jez

Reputation: 15359

"Generator comprehensions" are your friend. Not least because a "generator" only works on one element at a time, helping you save memory. Also, some time can be saved by pre-computing the relevant powers of 10 and performing integer arithmetic instead of converting to and from strings:

import itertools

digits = [0,1,2,3,4,5,6,7,8,9]
oom = [ 10 ** i for i, digit in enumerate( digits ) ][ ::-1 ] # orders of magnitude
allperm = itertools.permutations( digits )

firstpass = ( sum( a * b for a, b in zip( perm, oom ) ) for perm in allperm if perm[ 0 ] )

print sum( i for i in firstpass if i % 7 == 0 )

This is faster than the original by a large factor, but the factorial nature of permutations means that 15 digits is still a long way away. I get 0.05s for len(digits)==8, 0.5s for len(digits)==9, but 9.3s for len(digits)==10...

Since you're working in base 10, digits sequences of length >10 will contain repeats, leading to repeats in the set of permutations. Your strategy will need to change if the repeats are not supposed to be counted separately (e.g. if the question is phrased as "how many 15-digit multiples of 7 are repermutations of the following digits...").

Upvotes: 2

wenzul
wenzul

Reputation: 4058

Using itertools is a good choice. Well investigated.

I tried to improve the nice solution of @jez. I rearanged the range, replaced zip through izip and cached the lookup in a local variable.

N = 10
gr = xrange(N-1,-1,-1)
ap = itertools.permutations(gr)
o = [10 ** i for i in gr]
zip = itertools.izip
print sum(i for i in (sum(a*b for a, b in zip(p, o)) for p in ap if p[0]) if i % 7 == 0)

For me it's about 17% faster for N=9 and 7% for N=10. The speed improvement may is negligible for larger N's, but not tested.

Upvotes: 1

Gerrat
Gerrat

Reputation: 29710

There are many short-cuts in python you're missing. Try this:

import itertools

digits= [0,1,2,3,4,5,6,7]
digital=(itertools.permutations(digits))

mytuple=set()
for i in digital:
    if i[0] != 0:
        mytuple.add(int(''.join(str(d) for d in i)))

z = [i for i in mytuple if i%7==0]

print sum(z)

Might be hard to get to 15 digits though. 15! is 1.3 trillion...if you could process 10 million permutations per second, it would still take 36 hours.

Upvotes: 0

Related Questions