[Tutor] Dumb Luck with the Partitioning Problem

[Steven Burr]

--Apple-Mail-1476058108-1
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	format=flowed;
	charset=us-ascii

My bright idea on the partitioning problem was to try to arrive at a 
quick approximation of the best result, and then massage the resulting 
data sets to get closer to the target.  (It occurred to me later that 
this approach probably makes no sense, because for all I know the set of 
integers yielding the best result and the set yielding the next best 
result are completely different.)

So anyway, I decided that splitting the set of the integers from 1 to 50 
into evens and odds might be a good first approximation of the best 
result.  I then wrote an algorithm that found the combination of two 
numbers, one from each set, that would yield the greatest reduction in 
the difference between the sum of the squares.

Just these first two steps produced the following results:

First list:  [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 29, 31, 33, 
35, 37, 39, 41, 43, 45, 46, 47, 49]
Sum of square roots =  119.517524702
Second list:  [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 27, 28, 
30, 32, 34, 36, 38, 40, 42, 44, 48, 50]
Sum of square roots =  119.518275902
Distance from target =  0.000375600114126
Total time =  0.02

These results are actually better than those produced by Danny's method, 
which I can't even begin to understand, and not too far off from those 
produced by Tim's "brute force" approach.   I probably don't need to 
tell you, however, that this was pure, dumb (literally) luck.  I tried 
the same approach on other sets of integers, and the results are not 
nearly as impressive.

Every attempt I made to massage to the numbers further either went 
horribly wrong or made no progress.  At about 2:00 a.m. on the night 
Danny posted the problem, I tossed in the towel.  (Thanks so much, 
Danny. : )

My opus is attached for your amusement.  If there were a web site called 
"senseless python," I would make a submission.

--
third from the bottom
http://www.adeq.state.az.us/lead/staff.html

<Attachment missing>
--Apple-Mail-1476058108-1
Content-Type: multipart/mixed;
	boundary=Apple-Mail-96379525-2


--Apple-Mail-96379525-2
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=us-ascii;
	format=flowed

My bright idea on the partitioning problem was to try to arrive at a 
quick approximation of the best result, and then massage the resulting 
data sets to get closer to the target.  (It occurred to me later that 
this approach probably makes no sense, because for all I know the set of 
integers yielding the best result and the set yielding the next best 
result are completely different.)

So anyway, I decided that splitting the set of the integers from 1 to 50 
into evens and odds might be a good first approximation of the best 
result.  I then wrote an algorithm that found the combination of two 
numbers, one from each set, that would yield the greatest reduction in 
the difference between the sum of the squares.

Just these first two steps produced the following results:

First list:  [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 29, 31, 33, 
35, 37, 39, 41, 43, 45, 46, 47, 49]
Sum of square roots =  119.517524702
Second list:  [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 27, 28, 
30, 32, 34, 36, 38, 40, 42, 44, 48, 50]
Sum of square roots =  119.518275902
Distance from target =  0.000375600114126
Total time =  0.02

These results are actually better than those produced by Danny's method, 
which I can't even begin to understand, and not too far off from those 
produced by Tim's "brute force" approach.   I probably don't need to 
tell you, however, that this was pure, dumb (literally) luck.  I tried 
the same approach on other sets of integers, and the results are not 
nearly as impressive.

Every attempt I made to massage to the numbers further either went 
horribly wrong or made no progress.  At about 2:00 a.m. on the night 
Danny posted the problem, I tossed in the towel.  (Thanks so much, 
Danny. : )

My opus is attached for your amusement.  If there were a web site called 
"senseless python," I would make a submission.

--
third from the bottom
http://www.adeq.state.az.us/lead/staff.html


--Apple-Mail-96379525-2
Content-Disposition: attachment;
	filename="practice.py"
Content-Type: application/octet-stream;
	name="practice.py";
	x-unix-mode=0644
Content-Transfer-Encoding: 7bit

#-----PRELIMINARIES-----#

# Set the constant
N = 31

# Imports
from math import sqrt
from operator import add
import time

# Start the timer
start = time.clock()

# Func to find difference between sum of sqrts
def finddiff(first, second):
	return (
		    reduce(add, [t[1] for t in first]) -
		    reduce(add, [t[1] for t in second])
		   ) / 2


#-----APPROXIMATE BEST RESULT-----#

# Dividing between odds and evens seems like a good initial
# guess
first = [(x, sqrt(x)) for x in range(1, N, 2)]
second = [(x, sqrt(x)) for x in range(2, N, 2)]

# Find best result from switching two numbers
diff = finddiff(first, second)
bestresult = abs(diff)
for x in first:
	for y in second:
		currdiff = abs(x[1] - y[1] - diff)
		if currdiff < bestresult:
			bestresult = currdiff
			ind1 = first.index(x)
			ind2 = second.index(y)

# Change the lists to reflect approximation
first[ind1], second[ind2] = second[ind2], first[ind1]
first.sort()
second.sort()
sum1 = reduce(add, [t[1] for t in first])
sum2 = reduce(add, [t[1] for t in second])
target = reduce(add, [sqrt(x) for x in range(1, N)]) / 2

#-----GET CLOSER-----#

# Dismal failures deleted

#-----PRINT RESULT-----#

print "First list: ", [i[0] for i in first]
print "Sum of square roots = ", sum1
print "Second list: ", [i[0] for i in second]
print "Sum of square roots = ", sum2
print "Distance from target = ", max([sum1, sum2]) - target
print "Total time = ", time.clock() - start


--Apple-Mail-96379525-2--

--Apple-Mail-1476058108-1--