Partition problem From Wikipedia, the free encyclopedia
In computer science, the partition problem is an NP-complete problem. The problem is to decide whether a given multiset of integers can be partitioned into two "halves" that have the same sum. More precisely, given a multiset S of integers, is there a way to partition S into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2? The subsets S1 and S2 must form a partition in the sense that they are disjoint and they cover S. The optimization version asks for the "best" partition, and can be stated as: Find a partition into two subsets S1,S2 such that max(sum(S_1), sum(S_2)) is minimized (sometimes with the additional constraint that the sizes of the two sets in the partition must be equal, or differ by at most 1).
The partition problem is equivalent to the following special case of the subset sum problem: given a set S of integers, is there a subset S1 of S that sums to exactly t /2 where t is the sum of all elements of S? (The equivalence can be seen by defining S2 to be the difference S − S1.) Therefore, the pseudo-polynomial time dynamic programming solution to subset sum applies to the partition problem as well.
Although the partition problem is NP-complete, there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called the "The Easiest Hard Problem" by Brian Hayes.
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #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]
|
I have tried to solve the Partition Problem using the theory of natural selection. The solution is approximate and optimal, not the correct answer always, but to a larger extent. The solution uses the genetic methods of crossover and selective iterations. A few parameters like the number of iterations, selective percentage, crossover-ratio, etc are defined as constants and can be varied and experimented to best suite for a particular species and raw population.
This is the first version of the code, I intend to improve it further.
Constructive comments, feedback and criticism will be highly appreciated.
Why not just use DP?