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]. -- http://mail.python.org/mailman/listinfo/python-list
