Re^3: partition of an array

Thanks for the edge case.

A couple of possible fixes spring to mind:

Shuffling the input--not a guarentee.
Sorting the input--is there an equivalent edge case that would give non-optimum results starting from sorted ordring?
Splitting the input both ways--@a shorter than @b and vice versa--and finding the best solution from both datasets. Would that guarentee an optimum?

Things to play with. Thanks.

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: partition of an array

Replies are listed 'Best First'.
Re^4: partition of an array by Limbic~Region (Chancellor) on Mar 09, 2009 at 19:55 UTC
BrowserUk, Regarding #2 (sorting the input), this is also a bust. You have to sort in descending order for my original edge case to work but if you sort in descending order for the following test case it doesn't produce optimal results `7 7 7 1 0 0 0 -42 36 0 0 6 6 6 -28 __DATA__ 146 : [36 7 7 7 6 6 6 1] [0 0 0 0 0 -28 -42] 74 : [0 7 7 7 6 6 6 1] [36 0 0 0 0 -28 -42] 18 : [-28 7 7 7 6 6 6 1] [36 0 0 0 0 0 -42] 10 : [-42 7 7 7 6 6 6 1] [36 0 0 0 0 0 -28]` [download] It can be shown that without sorting the data, the following solution is possible: `46 : [7 7 7 1 0 0 0 -42] [36 0 0 6 6 6 -28] 12 : [36 7 7 1 0 0 0 -42] [7 0 0 6 6 6 -28] 2 : [36 0 7 1 0 0 0 -42] [7 7 0 6 6 6 -28]` [download] This means #1 is also out. Possibly #3 (running it both ways) would produce optimum results but I am not ready to convince myself of it. Cheers - L~R	[reply] [d/l] [select]
Re^4: partition of an array by Limbic~Region (Chancellor) on Mar 09, 2009 at 20:09 UTC
BrowserUk, Update: I started this node indicating that I believed that I had proven that running it both ways was not guaranteed to produce an optimal solution. Then I updated it saying I had made a mistake. Now I am updating it again, quite confident that I have indeed proven that just running it both ways is not guaranteed to provide an optimum solution. Consider the input: `7 6 7 0 0 0 7 0 6 0 1 -42 6 __DATA__ 56 : [7 6 7 0 0 0 7] [0 6 0 1 -42 6] 42 : [0 6 7 0 0 0 7] [7 6 0 1 -42 6] 30 : [0 0 7 0 0 0 7] [7 6 6 1 -42 6] 28 : [0 0 6 0 0 0 7] [7 7 6 1 -42 6] 18 : [0 0 1 0 0 0 7] [7 7 6 6 -42 6] 16 : [0 0 1 0 0 0 6] [7 7 7 6 -42 6]` [download] I believe that to "run it both ways", I simply need to swap the assignments of @a and @b. If that's the case, then you can see that this too produces the same incorrect result: `56 : [0 6 0 1 -42 6] [7 6 7 0 0 0 7] 42 : [7 6 0 1 -42 6] [0 6 7 0 0 0 7] 40 : [7 7 0 1 -42 6] [0 6 6 0 0 0 7] 28 : [7 7 6 1 -42 6] [0 0 6 0 0 0 7] 26 : [7 7 7 1 -42 6] [0 0 6 0 0 0 6] 16 : [7 7 7 6 -42 6] [0 0 1 0 0 0 6]` [download] I haven't found an input that breaks if you sort the list and run it both ways but I am not inclined to think that makes a difference. Cheers - L~R	[reply] [d/l] [select]