not homework... something i find an interesting problem

[Trip Technician]

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 !