not homework... something i find an interesting problem

[MRAB]

Trip Technician wrote:
> Thank you Dave. This does it but slowly. takes every subset of the
> list a of squares, 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].