Trip Technician wrote:
although it's not homework (how can i prove that...?) i am still happy
with just hints
+++
we want to express integers as sums of squares. (repeated squares are
allowed)
most numbers have one minimal representation e.g. 24=16+4+4, some have
two or more e.g. 125 = 121+4 = 100+25
so far I have created a simple recursive function that expresses a
given number as a sum of squares in the obvious and naive way. it
returns a nested tuple , which is then flattened for simplicity...then
to cover the possibility that there might be one other minimal
representation i call another similar function which will find one
other representation, not necessarily shorter or of equal length,
finally these are sorted and the results displayed, with the minimal
result or the 2 equal-length minimal results.
as the numbers get bigger (i believe) there will be some which have 3
or more minimal representations which this code will miss.
what I want to do is come up with a recursion that will find all
possible minimal representations in one function (if possible ) in an
optimally elegant and scalable way. There's no application in mind, i
just love playing with math.
code so far below:
# express numbers as sum of squares
a=[x**2 for x in range(50,0,-1)]
# finds obvious candidate
def squ(z):
if z==0:
return 0
for x in a:
if z>=x:
return x,squ(z-x)
# finds another candidate with largest square as next square down from
above function
def squ2(z):
if z==0:
return 0
for x in a:
if z>=x:
return a[a.index(x)+1],squ(z-a[a.index(x)+1])
def flatten(lst):
for elem in lst:
if type(elem) in (tuple, list):
for i in flatten(elem):
yield i
else:
yield elem
q=[]
r=[]
for aa in range(100):
r.append([])
for xx in range(10,100):
q=[]
for ss in flatten(squ(xx)):
if ss!=0:
q.append(ss)
r[xx].append(q)
for xx in range(10,100):
q=[]
for ss in flatten(squ2(xx)):
if ss!=0:
q.append(ss)
r[xx].append(q)
for eee in r:
if eee:
if len(eee[0])==len(eee[1]):
print r.index(eee),eee[0],eee[1]
else:
print r.index(eee),eee[0]
You said you'd be happy with hints. So I'd suggest doing it with
generators. If a generator calls itself recursively, and if it's 'yield
value' is a list, then the main program simply invokes the generator in
a for loop, storing any solution that's the same length as the best so
far, or replacing its current set with a new one if it's better.
Just getting a complete set of results, but not checking for the min
one, my main code is:
def main(target):
for i, res in enumerate(solutions(target, target)):
print i, res
So I have a generator called solutions(), which takes two parameters.
First one is the target
value, second one is a limit value we don't want to exceed for any
remaining square. This throws out results that are out of sorted order,
and for my test value of 33, reduces the number of values to examine
from 30000+ to 33. (That number is a coincidence)
I could give you the recursive generator as well, it's only 8 lines.
But then I'd take away your fun. The only other code I needed was your
list "a" of squares.
No optimizations as yet. So for example, I go through the whole list a,
skipping any that are greater than either target or limit. Clearly, I
could use an index to save some of that. But if I tried such at this
point, I'd have to do timings to make sure it'd actually be a net gain.
For 33, it got 33 lists, in .0039 secs. For 100, it got 1115 lists, in
.66 secs.
--
http://mail.python.org/mailman/listinfo/python-list
