1

I'm solving a practice problem for algorithm study and looking for the fastest implementation for the problem below.

Given there is a list L of positive one digit integers of length N, define three points A, B, and C in L so that the list is divided into three partitions. Note that A < B < C in terms of indices. The first partition is all elements between A and B, the second partition is between B and C, and the third partition is all other elements.

Then let h, i, and j be the sum of each partition. I want to find a the minimal value of max([h, i, j]) - min([h, i, j]) in all possible partitioning.

For example, if L = [4, 5, 6, 7, 6, 5, 4], then the portioning will be

a = [6, 7]
b = [6, 5]
c = [4, 5, 4] # reminder 

# because
h = sum(a) -> 13
i = sum(b) -> 11
j = sum(c) -> 13

# that minimize the difference
max([h, i, j]) - min([h, i, j]) -> 2

The only way I currently came up with is to brute force all possible partitioning so that

current_min = sum(L)
N = len(L)

for A in range(N):
    for B in range(A, N):
        for C in range(B, N):
            sum_1 = sum(L[A:B])
            sum_2 = sum(L[B:C])
            sum_3 = sum(L[:A]) + sum(L[C:])
            sums = [sum_1, sum_2, sum_3]
            if max(sums) - min(sums) < current_min:
                current_min = max(sums) - min(sums)

But I can see that my solution isn't ideal. Is there any faster way?

TFC
  • 466
  • 1
  • 5
  • 14
  • Does this answer your question? [How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?](https://stackoverflow.com/questions/32437090/how-to-partition-an-array-of-integers-in-a-way-that-minimizes-the-maximum-of-the) – Mohammad Aug 15 '21 at 18:49
  • No, that is a similar question but in my question, the objective is to minimize is the difference between the sum of the smallest portion and the sum of the largest partition. So that minimizing the maximum of is not sufficient, it is also required to maximize the minimum of sum of smallest partition. In fact, the answer in the first test case in that question is {2, 1}, {5, 1}, {2, 2, 2} that is not the answer for my question, it should be {2, 2, 1}, {5, 1}, {2, 2}. – TFC Aug 15 '21 at 19:00

1 Answers1

0

Here is an approach, You could calculate the total sum. Calculate 1/3rd of the sum. Now iterate through the list and keep adding the element to sum1 till it just exceeds 1/3rd of the sum (check that at least 2 elements remain). This makes 1 partition. Now similarly, keep adding the element to the sum2 till it just exceeds 1/3rd of the sum. The remaining elements constitute partition 3.

Now you can repeat the procedure in reverse order and see whichever set of max([h, i, j]) - min([h, i, j]) gives the minimal value.

The idea is to keep the difference between the sum of partitions as small as possible. This will automatically ensure that difference between max and min of sums is least.

Srishti Ahuja
  • 181
  • 1
  • 7
  • Im sorry if I misunderstand your idea but does it work for the test case in the question? Because the first partition is not always begin from the left or right end of the list, you need to find where the first partition begin i.g. for list [a, b, c, d, e, f] the partitions might be [b,c] [c,d] and [a,f] (beginning of the first partition is a). So you can not just start adding from a to f. – TFC Aug 15 '21 at 19:25
  • I'm sorry, I thought we had to start partitioning from the first element – Srishti Ahuja Aug 15 '21 at 21:29