not homework... something i find an interesting problem

[MRAB]

Trip Technician wrote:
> On 21 Apr, 14:46, MRAB <goo... at mrabarnett.plus.com> wrote:
>> Trip Technician wrote:
>>> Thank you Dave. This does it but slowly. takes every subset of the
>>> list a ofsquares, and then gets a 'partition' that will work, many
>>> are very inefficient (with lots of 1s).
>>> any hints about how to speed up ?
>>> def subset(x):
>>>     for z in range(1,2**len(x)):
>>>         q=bin(z)
>>>         subs=[]
>>>         for dig in range(len(q)):
>>>             if q[dig]=='1':
>>>                 subs.append(x[dig])
>>>         yield subs
>>> def bin(x):
>>>   q=""
>>>   while x>=1:
>>>     q+=str(x%2)
>>>     x//=2
>>>   return q
>>> def squ(z,b):
>>>     if z==0:
>>>         return 0
>>>     for x in b:
>>>         if z>=x:
>>>             return x,squ(z-x,b)
>>> def flatten(lst):
>>>     for elem in lst:
>>>         if type(elem) in (tuple, list):
>>>             for i in flatten(elem):
>>>                 yield i
>>>         else:
>>>             yield elem
>>> sizelim=150
>>> a=[x**2 for x in range(int(sizelim**0.5),1,-1)]
>>> q,r=[],[]
>>> for aa in range(sizelim):
>>>     r.append([])
>>> for xx in range(1,sizelim):
>>>     for z in subset(a):
>>>         q=[]
>>>         z.append(1)
>>>         for rr in flatten(squ(xx,z)):
>>>             if rr !=0:
>>>                 q.append(rr)
>>>         item=[len(q),q]
>>>         if item not in r[xx]:
>>>             r[xx].append(item)
>>>             r[xx].sort()
>>> for eee in r:
>>>     if eee:
>>>             print r.index(eee),eee[0:3]
>> Even this code doesn't find them all! For 135 it finds [49, 49, 36, 1],
>> [81, 25, 25, 4] and [81, 36, 9, 9], but not [121, 9, 4, 1].- Hide quoted text -
>>
>> - Show quoted text -
> 
> blowed if i know why that is !
> 
I think I might have cracked it:

import math

def sumsq(n):
     if n == 0:
         return [[]]
     root = int(math.sqrt(n))
     square = root ** 2
     sums = [[square] + s for s in sumsq(n - square)]
     while root > 1:
         root -= 1
         square = root ** 2
         if square < n // len(sums[0]):
             break
         more_sums = [[square] + s for s in sumsq(n - square)]
         if len(more_sums[0]) == len(sums[0]):
             sums.extend(more_sums)
     return sums

for n in range(1, 150):
     # Find all the possible sums.
     sums = sumsq(n)
     # Create a set of the unique combinations.
     sums = set(tuple(sorted(s, reverse=True)) for s in sums)
     # Convert back to a list of lists.
     sums = [list(s) for s in sorted(sums, reverse=True)]
     print n, sums