[Tutor] My shot at the partitioning problem

[Tim Peters]

Here's something to goad you to greater heights.

As dumb as possible:  just generate random permutations of the inputs, and
for each one do the dumbest possible thing with it to try to get close to
the goal.  No intelligence, just brute force -- but lots of it <wink>.

Here's a *poor* run (btw, it stops itself after 10 seconds -- and this is a
pretty fast machine, and with a version of Python quicker than 2.1.1):

Did 11790 trials in 10.05 seconds.
Sum 119.51764944760885, distance from target 0.00025085415153114354.
This is the sum of the sqrts of
     [1, 2, 3, 5, 6, 10, 11, 12, 14, 16, 17, 18, 19, 20, 21, 23,
      24, 26, 28, 29, 36, 38, 40, 42, 46, 48, 50]

A more typical run gets within 6e-5 of the target.  Here's an exceptionally
(but not supernaturally) good run:

Did 11702 trials in 10 seconds.
Sum 119.51789179229621, distance from target 8.5094641661953574e-006.
This is the sum of the sqrts of
     [1, 2, 5, 6, 12, 13, 15, 16, 17, 18, 21, 23, 27, 29, 31, 32,
      34, 35, 39, 41, 42, 43, 45, 47, 48]

When it comes to computer searches, doing a stupid thing quickly but many
times is often more effective than doing an intelligent thing slowly --
that's one of the surprising lessons learned from computer chess, but is due
in part to that writing a *truly* intelligent thing is much more difficult
than is first imagined.

There are several ways to improve this stupid algorithm by making it a
*little* more intelligent, but not *too* intelligent -- if you make it smart
enough that it runs, say, 10x slower per trial, then it had better be *so*
much smarter that it makes up for running it 10x less often.  That's a
difficult thing to judge in advance!  So don't even bother:  Just Try It,
*whatever* you think of.  Then think of something else, and try that too.
Repeat until you stumble into a Major Breakthrough <wink>.

import math
import random
import time

N = 50
roots = [(i, math.sqrt(i)) for i in range(1, N+1)]

sum = 0.0
for i, root in roots:
    sum += root
target = sum / 2

# Return a subset of vector and its sum (<= target).
def greedy(vector, target):
    result = []
    sum = 0.0
    for i, value in vector:
        newsum = sum + value
        if newsum <= target:
            sum = newsum
            result.append((i, value))
    return result, sum

start_time = time.time()
best_sum = -1.0
best_subset = None
ntrials = 0
while time.time() - start_time < 10.0:
    ntrials += 1
    random.shuffle(roots)
    subset, sum = greedy(roots, target)
    if sum > best_sum:
        best_sum = sum
        best_subset = subset

print "Did %d trials in %g seconds." % (ntrials, time.time() - start_time)
print "Sum %r, distance from target %r." % (best_sum, target - best_sum)
best_subset.sort()
print "This is the sum of the sqrts of"
print "    ", [i for (i, value) in best_subset]

in-the-end-a-billion-mindless-insects-can-devour-anyone<wink>-ly y'rs
    - tim