Re^3: Divide array of integers into most similar value halves

Thanks. That is indeed a bug. The (lightly tested) fix is to change the last line of the sub to:

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

Basically, because the sub only stores one best partition, when it runs out of iterations, it needs to filter the input array to generate teh other half. The filter was a sloppy variation on a theme that works for other purposes but not this. I think the above corrects it, but I will need to give more thought once my brain has awoken.

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.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

Comment on Re^3: Divide array of integers into most similar value halves Download Code

Replies are listed 'Best First'.
Re^4: Divide array of integers into most similar value halves by Pepe (Sexton) on Sep 04, 2008 at 14:46 UTC
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	[reply]
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]
Re^6: Divide array of integers into most similar value halves by Pepe (Sexton) on Sep 04, 2008 at 18:44 UTC
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]
Re^7: Divide array of integers into most similar value halves by tilly (Archbishop) on Sep 04, 2008 at 19:14 UTC
Re^8: Divide array of integers into most similar value halves by Pepe (Sexton) on Sep 04, 2008 at 19:46 UTC
Some notes below your chosen depth have not been shown here
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. "Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."	[reply] [d/l]
Re^6: Divide array of integers into most similar value halves by Pepe (Sexton) on Sep 04, 2008 at 15:07 UTC
Sorry It seems to do worse. Some of the elemenents appear if both of the resulting subarrays	[reply]
Re^7: Divide array of integers into most similar value halves by BrowserUk (Patriarch) on Sep 04, 2008 at 15:57 UTC
Re^8: Divide array of integers into most similar value halves by Pepe (Sexton) on Sep 04, 2008 at 16:04 UTC
Some notes below your chosen depth have not been shown here
Re^4: Divide array of integers into most similar value halves by Pepe (Sexton) on Sep 03, 2008 at 22:35 UTC
I'll try it for you and report on it when I'm done. Maybe tomorrow. Thanks again fro your effort	[reply]