NP-complete sometimes isn'tby tilly (Archbishop)
|on Sep 02, 2008 at 05:56 UTC||Need Help??|
Recently Pepe asked an interesting question at Divide array of integers into most similar value halves. Given an array of integers he wanted to split it into two sub-arrays whose sum was as close as possible together. Many people informed him that this was a very hard problem, references were provided showing that this solves the Partition Problem, which is known to be NP-complete. Luckily Pepe did not need an exact answer, and there is a greedy algorithm that was good enough for his needs.
What makes this problem interesting is that the many confident answers and external references notwithstanding, the actual problem the OP has is almost certainly not NP-complete! As proof I have an implementation on my computer that reliably partitions an array of 100 random integers of size 0-999 in under 7 seconds. That is, the the following code reliably runs in under 7 seconds and is guaranteed to find the best answer:
How is this possible?
The trick is that when it comes to NP-complete problems, the devil is in the details. If you change even one detail of the problem, what was NP-complete can suddenly become much more tractable. Sometimes the detail is so easy to miss as to be virtually impossible to see. Such is the case here.
The relevant detail in this case is that we are dealing with an array of small integers. If we have 100 integers in the range 0-1000 in side and look at the partitions, the difference of the size of the two partitions has to be in the range -100,000 to 100,000. Of course there are 2100 possible partitions, but the same difference in sizes will show up from many, many possible partitions. But we don't care about enumerating the possible partitions, only the possible sizes. And while a range of 200,000 possible sizes is not exactly small, it is still tractable.
With arbitrary integers this idea would fail hard, because nothing stops you from having integers of size 2100. But in the real world when we say "integer", we usually don't actually mean "arbitrary integer". We mean "small integer" and that difference can be important.
In this case it looks like we want to create a hash of possible differences in the sum of the partitions. The point of a hash will find and eliminate unneeded duplicate ways of getting the same difference, keeping the problem down to a reasonable size. A back of the envelope estimate says that if we do it right, performance should be O(n2) in the size of the initial dataset. (A darned sight better than the naive 2O(n)!) After handling a few technical details, that leads to the following naive implementation that reliably runs on my laptop in about 20 seconds:
Of course 20 seconds is a little slower than I'd like. So I reasoned that most of my time is spent looking at partitions that I should know are not going to lead to the best answer. So I figured that I should first try to find a greedy solution, and then skip any partial partition which could not possibly match the greedy one when it is filled out. Of course this filtering would be most effective if I put the biggest numbers first, because the sume of a few big numbers at the start could be as big as the sum of many little numbers at the end.
Of course when I implemented this I also noticed that often you did find a perfect partition. So I added a check for whether the starting partition we have plus the rest of the initial greedy partition is a perfect partition. If it is, then stop immediately. In that case you get the right answer virtually instantaneously.
This version often finishes in a couple of hundredth's of a second, and the rest of the time finishes on my laptop in under 7 seconds. The code is kind of long, so I'll hide it.So the next time you think you have an NP-complete problem, before throwing your hands up in despair, think about whether there is anything, anything at all, that you can possibly use to turn it into a much simpler problem. Usually you will fail, but every so often you'll get lucky. As in this case.