Re^2: partition of an array

BrowserUk,
I really like this approach, but it is flawed. Consider the input:

7 7 7 1 0 0 0 -42 0 0 6 6 6
[download]

There are 13 items so we will have one partition of 6 and one of 7. your code produces the following solution:

46 : [7 7 7 1 0 0 0] [-42 0 0 6 6 6]
32 : [0 7 7 1 0 0 0] [-42 7 0 6 6 6]
18 : [0 0 7 1 0 0 0] [-42 7 7 6 6 6]
16 : [0 0 6 1 0 0 0] [-42 7 7 7 6 6]
[download]

The first partition sums to 7 and the second to -9 with a difference of 16. You could move (not swap) the 6 in the first partion to the second partition and you would end up with:

4 : [0 0 1 0 0 0] [-42 7 7 7 6 6 6]
[download]

The first partition now sums to 1 and the second to -3 for a difference of 4. I don't know the difficulty in accounting for this situation but the problem is assuming the only balancing operation is swapping.

Cheers - L~R

Comment on Re^2: partition of an array Select or Download Code

Replies are listed 'Best First'.
Re^3: partition of an array by BrowserUk (Patriarch) on Mar 09, 2009 at 19:34 UTC
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."	[reply]
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]