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

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.

  • Comment on Re^7: Divide array of integers into most similar value halves

Replies are listed 'Best First'.
Re^8: Divide array of integers into most similar value halves
by Pepe (Sexton) on Sep 04, 2008 at 19:46 UTC
    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]
        Listen tilly,
        Unbelievable! Everytime there's a conflict with the other scripts yours gets it right. Hat tip to you, tilly!
        I must only use it when the others fail because of the time problem, but I'm sure it will do the work right.
        It's gone now through 20.000 arrays and not a single problem.
        Also, the decimal numbers in the values can only be .5, which I understand is fine for the script.
        Thank you so much.

        Pepe
[reply]

In Section Seekers of Perl Wisdom