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

BrowserUk,
Your algorithm is the best I found so far, but it still has the bug with repeated numbers.
I came out with a suboptimal solution, but in more than 100.000 arrays your code wins in every case the answer are different and there are no repeated elements.
Now it does it only with more than 2 repetitions as in @array = (57,57,57,43,32). Would there be any way of solving that bug for any array no matter how many repeated elements it contains?
I've tried but I don't seem to be able to do it. Your code is really tight and it's difficult for me to modify it.
Sorry for the bugging. I really appreciate your efforts.
Pepe
  • Comment on Re^4: Divide array of integers into most similar value halves

Replies are listed 'Best First'.
Re^5: Divide array of integers into most similar value halves
by tilly (Archbishop) on Sep 04, 2008 at 17:40 UTC
    Did you try my algorithm at Re^2: NP-complete sometimes isn't (A benchmark)? It is guaranteed to always find the best possible answer. It has no bug with repeated numbers. It is not the fastest option, but it may well be fast enough for your purposes.
[reply]
      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.
[reply]
        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]
Re^5: Divide array of integers into most similar value halves
by BrowserUk (Patriarch) on Sep 04, 2008 at 15:01 UTC

    Sorry. I never got back to checking the fix properly.

    Would you please try replacing the last line with this (note:pre-decrement not post-decrement). 

        return \@best, [ grep{ !exists $seen{ $_ } or !--$seen{ $_ } } @$a
+Ref ];

    [download]
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
      Sorry
      It seems to do worse. Some of the elemenents appear if both of the resulting subarrays
[reply]

        Grr! Intersection & difference of arrays is something that ought to be in core.

        Looked in List::MoreUtils to no avail.

        I looked at cpan and downloaded Array::Utils but it can't handle duplicates.

        Looked at List::Compare, but it comes complete with the kitchen sink & waste disposal (aliased as Belfast Sink & waste bin) and calculates 20 different things under the guise of "initalising".

        Could you post an example of input array and expected outputs please.

        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]

In Section Seekers of Perl Wisdom