in reply to Re^5: Divide array of integers into most similar value halves
in thread Divide array of integers into most similar value halves

Hey tilly,

I haven't tried that one. In fact I hadn't even notice there was another node with that theme! I looked for hours before my first post, but I guess the name of the node didn't appeal to me, since I did not even know about teh existence of NP-complete problems.
It's pretty long and seems slow but it may be the answer to my prays. I hope it doesn't take days...
I'll try it.
Thanks.
Pepe.
  • Comment on Re^6: Divide array of integers into most similar value halves

Replies are listed 'Best First'.
Re^7: Divide array of integers into most similar value halves
by tilly (Archbishop) on Sep 04, 2008 at 19:14 UTC
    I wrote that thread after yours because I thought it of independent interest for people who weren't following your problem. I posted a pointer to that thread from yours, but I guess you missed the pointer.

    Please do get back to me and tell me whether that solution was fast enough for you.

[reply]
      Oh! I see...
      Sorry for missing the post, I woulded try before.
      I just tried now and it does awesome in terms of getting it right every single time. It takes a while in the most difficult cases, but it's pretty fast overall and I think I can live with it being slow only sometimes.
      The problem came when it found this:

      @array = (8,45.5,42.5,68,42,31.5,19);

      If it's too much of a problem I think I could round up all the decimals before passing it to the array.

      Thanks a lot for trying.
      Pepe.
[reply]
        That is due to the hash -> array optimization. If I undo that then I get (lightly tested):
        Read more... (3 kB)
        I think it works, but you should test with a bunch of random arrays to see that it gives answers as good as my previous code.

        Do note, however, that if you are throwing in very random decimals in there (eg things like 43.12314 and 25.5422431) that the run-time performance is going to degrade horribly. That's because the basic problem really is NP-complete, and when the sums of various subsets can take on a great many different values (rather than being limited to a fairly small number of numbers) then the optimization that I am using to make the special case tractable breaks down. Therefore if you will have numbers that are not multiples of some fairly small fraction, you need to round them before passing them into that function.

[reply]
[d/l]

In Section Seekers of Perl Wisdom