#http://en.wikipedia.org/wiki/Partition_problem
import random
import logging
logging.basicConfig(level = logging.DEBUG)
log = logging.getLogger('partitionselection')
CROSSOVER_FRACTION = 0.20
SELECTIVE_FRACTION = 0.50
VARIANTS = 5
POPULATION_SIZE = 20
ITERATIONS = 100

def crossover(a,b):
    ml = min([len(a), len(b)])
    used_indices = []
    for i in range(0, int(ml*CROSSOVER_FRACTION)): 
        ra = random.randint(0,ml-1)
        while ra in used_indices:
            ra = random.randint(0,ml-1)
        a[ra], b[ra] = b[ra], a[ra]
        used_indices.append(ra)
    return (abs(sum(a)-sum(b)), a, b)

def naturalselection(partition_traids):
    global least_diff
    new_partition_traids = partition_traids [:]
    for partition_traid in partition_traids:
        for i in range(VARIANTS):
            variant = crossover(*partition_traid[1:])
            if variant[0]<least_diff:
                new_partition_traids.append(variant)
    new_partition_traids.sort()
    least_diff = new_partition_traids[0][0]
    remaining_partition_triads = new_partition_traids\
        [:int(POPULATION_SIZE*SELECTIVE_FRACTION)]
    return remaining_partition_triads
                     
if __name__ == '__main__':
    least_diff = 99999999
    import simplejson
    #assumes that the file named "population" has the raw 
    #population, a python list dumped with simplejson
    population = simplejson.loads(file('population').read())
    n = len(population)
    partition_a, partition_b = population[:n/2], population[n/2:]
    partition_traids = [(abs(sum(partition_a)-sum(partition_b)), partition_a, partition_b)]
    for i in range(ITERATIONS):
        partition_traids = naturalselection(partition_traids)
    print least_diff, partition_traids[0]