1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
|
# version de base
def sums1(n):
def sumrec(n,m):
if n == 0: return [()]
else:
return [(i,)+j for i in xrange(1,min(m,n)+1) for j in sumrec(n-i,i)]
return sumrec(n,n)
# avec mémoization
def memoize(f):
mem={}
def memo(*args):
if args not in mem:
mem[args] = f(*args)
return mem[args]
return memo
def sums2(n):
@memoize
def sumrec(n,m):
if n == 0: return [()]
else:
return [(i,)+j for i in xrange(1,m+1) for j in sumrec(n-i,min(i,n-i))]
return sumrec(n,n)
# avec un générateur
def sums3(n):
def sumrec(n,m):
if n == 0: yield ()
else:
for i in xrange(1,min(m,n)+1):
for j in sumrec(n-i,i): yield (i,)+j
return sumrec(n,n)
# version plus impérative (?)
def sums4(nn):
mem = {(0,0): [()]}
for n in xrange(1,nn):
for m in xrange(1,min(n,nn-n)+1):
mem[(n,m)] = [(i,)+j for i in xrange(1,m+1) for j in mem[(n-i,min(i,n-i))]]
return [(i,)+j for i in xrange(1,nn+1) for j in mem[(nn-i,min(i,nn-i))]]
import timeit
print "sums1",
print timeit.Timer("sums1(64)","from __main__ import sums1").timeit(1)
print "sums2",
print timeit.Timer("sums2(64)","from __main__ import sums2").timeit(1)
print "sums3",
print timeit.Timer("for x in sums3(64): pass","from __main__ import sums3").timeit(1)
print "sums4",
print timeit.Timer("sums4(64)","from __main__ import sums4").timeit(1) |
Partager