Optimized Partition

This is my submission for Nondeterministic November - itch.io .

I tried to write a program that could solve a variety of NP-complete problems in different ways and benchmark the results.  Unfortunately, that's not what actually happened.

I have a program, but it does... not much.  I never finished the code for generating the random partition problems to be solved, so I had to make something quickly on the last day.

My submission consists of 2 Java files in a zip file.  PartitionProblem includes a method optimizedPartitionSolution that is intended to solve the partition problem (see Partition problem - Wikipedia).  It is completely untested, and I coded it in one afternoon.  The other file is IntArrayList, which is provides some bare minimum functionality for a resizable array of integers.

It did compile, but I had to change it slightly to cut it out of my program.  I can almost guarantee that there is some sort of bug.  I'm positive that it's screwed up in some way because I wrote the entire thing all at once with no testing and no iteration.  I don't intend to fix it in the immediate future because I'm behind on other projects.

This is an outline of the algorithm.

Consider the binary representations of the integers in the multiset to be partitioned.  There's some maximum number of bits that the integers might have (in my case, 31 because I'm not using the sign bit).

Create a bucket for each potential bit.  Check each integer in the multiset.  Put each integer in the bucket corresponding to the least significant bit that is a 1.

The point of this is to do something like radix sort but with partition.  The least significant bit of the sum is determined by the integers that have 1s for their least significant bits.  In other words, the odd numbers determine whether the sum is odd.  If the odd numbers are processed first, then there's no need to check sums that have the wrong number of odd numbers in the sum.

After doing the numbers that end in 1, do the numbers that end in 10, then the numbers that end in 100, and so on.

There is a second trick in this.  There's the party bin and the trash bin.  The party bin is the part of the partition that the program is trying to find, and the trash bin is the other part.

If an integer is too large to fit in the party bin, it gets thrown in the trash bin.  Alternatively, if an integer is too large to fit in the trash bin, it gets thrown in the party bin.

The worst case performance is O(2^n), just like brute force.  However, this solution should be faster on random data.  It would never be as fast as dynamic programming, but it doesn't require a giant table.  It doesn't matter how large the numbers, and it should be multi-threadable.  I think the same algorithm would work for subset sum with slight modifications to the beginning.

It is kind of a dead end.