in reply to NP-complete sometimes isn't

and is guaranteed to find the best answer

I think you may have a bug. Given the input set [400 402 521 735 758 191 191 307 679 776 877], your code produces this partition: 

[400 402 521 735 758 191] := 3007
[191 307 679 776 877] := 2830

[download]

But there is a better partition: 

[679 776 307 877 191] := 2830
[400 402 521 758 735] := 2816

[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."

Replies are listed 'Best First'.
Re^2: NP-complete sometimes isn't
by tilly (Archbishop) on Sep 02, 2008 at 08:34 UTC
    The initial version that I posted did indeed have a bug. If it wound up not using any of the initial greedy guess, it would repeat the last element from the greedy guess. In your case that would explain why 191 repeated.

    I fixed that bug, but obviously not before you downloaded the buggy version of the code.

[reply]

      Indeed the updated version works much better. I was a bit quick of the mark because I was looking to use your code to verify the veracity of the claims I was making for my own :)

      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]
Re^2: NP-complete sometimes isn't
by shmem (Chancellor) on Sep 02, 2008 at 09:39 UTC
    Given the input set [400 402 521 735 758 191 191 307 679 776 877]

    Is the algorithm supposed to weed out duplicates from its input?

[reply]

      No. I produce the "input list" shown in my post, by combining the partitions output from tilly's code. (Because it wasn't actually displayed anywhere.)

      But, as tilly explained, under certain circumstances, the OP code he posted contained a bug that meant it would duplicate one value. He quickly corrected that problem, but not before I downloaded and ran his code.

      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]
Re^2: NP-complete sometimes isn't
by lidden (Curate) on Sep 02, 2008 at 07:44 UTC
    Your second output has one value less then the first one.
[reply]

In Section Meditations