not homework... something i find an interesting problem
MRAB
google at mrabarnett.plus.com
Tue Apr 21 15:46:16 CEST 2009
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].
More information about the Python-list
mailing list