Re^3: NP-complete sometimes isn't (A benchmark)

Can I offer a suggestion. Okay, I'm going to offer a suggestion, whether you will have the time or inclination to do anything with it... :)

I think it would greatly simplify and optimise your algorithm to avoid the conditionals associated with negative numbers. You can do that by applying a simple sort to the inputs and then adjusting the whole array to make it all positive (and undo it on output):

sub partition {
    my @numbers - sort{ $b <=> $a } @_;
    my $adjust = 0;
    if( $numbers[ -1 ] < 0 ) {
        $adjust = - $number[ -1 ];
        $_ += $adjust for @numbers;
    }
     
    ...

    $_ -= $adjust for @part_1, @part_2;
    return \@part_1, \@part_2;
}
[download]

Note: I attempted to make this change and offer it back to you, but there is something about your algorithm that I am not understanding, because my attempts disappear up their own jackssies (sp?:).

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: NP-complete sometimes isn't (A benchmark) Download Code

Replies are listed 'Best First'.

Re^4: NP-complete sometimes isn't (A benchmark)
by tilly (Archbishop) on Sep 04, 2008 at 15:16 UTC

I did think about making all numbers be their absolute value, and then reverse which partition the negative numbers go in, but that logic looked more complicated and convoluted than the way I originally wrote it.

[reply]


Do you know where your variables are?
	PerlMonks