bearophileh...@lycos.com wrote:
MRAB:
I think I might have cracked it:
...
print n, sums
Nice.
If you don't want to use dynamic programming, then add a @memoize
decoration before the function, using for example my one:
http://code.activestate.com/recipes/466320/
And you will see an interesting speed increase, even if you don't use
Psyco ;-)
I discovered I hadn't got it quite right (it still missed some). Here's
the fixed code:
import math
def sumsq(n, depth=0):
if n == 0:
return [[]]
root = int(math.sqrt(n))
square = root ** 2
sums = [[square] + s for s in sumsq(n - square, depth + 1)]
while root > 0:
square = root ** 2
if square * len(sums[0]) < n:
break
more_sums = [[square] + s for s in sumsq(n - square, depth + 1)]
if len(more_sums[0]) == len(sums[0]):
sums.extend(more_sums)
elif len(more_sums[0]) < len(sums[0]):
sums = more_sums
root -= 1
sums = set(tuple(sorted(s, reverse=True)) for s in sums)
sums = [list(s) for s in sorted(sums, reverse=True)]
return sums
for n in range(1, 150):
print n, sumsq(n)
--
http://mail.python.org/mailman/listinfo/python-list
