Splitting list into 2 parts, as equal to sum as possible

Question

I'm trying to wrap my head around this whole thing and I can't seem to figure it out. Basically, I have a list of ints. Adding up those int values equals 15. I want to split up a list into 2 parts, but at the same time, making each list as close as possible to each other in total sum. Sorry if I'm not explaining this good.

Example:

list = [4,1,8,6]

I want to achieve something like this:

list = [[8, 1][6,4]]

adding the first list up equals 9, and the other equals 10. That's perfect for what I want as they are as close as possible.

What I have now:

my_list = [4,1,8,6]  

total_list_sum = 15

def divide_chunks(l, n): 
  
    # looping till length l 
    for i in range(0, len(l), n):  
        yield l[i:i + n] 
n = 2

x = list(divide_chunks(my_list, n)) 
print (x)

But, that just splits it up into 2 parts.

Any help would be appreciated!

Does this answer your question? [Algorithm to find which number in a list sum up to a certain number](https://stackoverflow.com/questions/3420937/algorithm-to-find-which-number-in-a-list-sum-up-to-a-certain-number) — fdermishin, Nov 26 '20 at 18:45
@Jonathon if your input is `[1,1,1,3]`, is `[[1,1,1],[3]]` a valid output? — Pablo C, Nov 26 '20 at 18:47
technically yes, but It needs to be split into 2 lists. Even if the total sum of each list is slightly off — Jonathon, Nov 26 '20 at 18:52
You could sort the list in any order, remove the first and last element, pair them. then take, remove the next first and last elements, till your list becomes empty — illusion, Nov 26 '20 at 19:00
This question was asked multiple times on StackOverflow: [Python](https://stackoverflow.com/questions/28602338/split-array-to-approximately-equal-chunks), [C#](https://stackoverflow.com/questions/44158174/split-int-array-into-two-arrays), [PHP](https://stackoverflow.com/questions/6758902/split-array-into-half-with-equal-or-approximately-equal-array-sum) — fdermishin, Nov 28 '20 at 11:17

Alain T. · Accepted Answer · 2020-11-27T17:34:52.177

You could use a recursive algorithm and "brute force" partitioning of the list. Starting with a target difference of zero and progressively increasing your tolerance to the difference between the two lists:

def sumSplit(left,right=[],difference=0):
    sumLeft,sumRight = sum(left),sum(right)

    # stop recursion if left is smaller than right
    if sumLeft<sumRight or len(left)<len(right): return

    # return a solution if sums match the tolerance target
    if sumLeft-sumRight == difference:
        return left, right, difference

    # recurse, brutally attempting to move each item to the right
    for i,value in enumerate(left):
        solution = sumSplit(left[:i]+left[i+1:],right+[value], difference)
        if solution: return solution

    if right or difference > 0: return 
    # allow for imperfect split (i.e. larger difference) ...
    for targetDiff in range(1, sumLeft-min(left)+1):
        solution = sumSplit(left, right, targetDiff)
        if solution: return solution 
    
# sumSplit returns the two lists and the difference between their sums

print(sumSplit([4,1,8,6]))     # ([1, 8], [4, 6], 1)
print(sumSplit([5,3,2,2,2,1])) # ([2, 2, 2, 1], [5, 3], 1)
print(sumSplit([1,2,3,4,6]))   # ([1, 3, 4], [2, 6], 0)

Please replace the last loop by `for targetDiff in range(difference+1, sumLeft-min(left)+1):`. Otherwise stack overflow happens — fdermishin, Nov 26 '20 at 23:42
That wasn't the issue (the function should not get to that loop when difference is not zero). Fixed it now. — Alain T., Nov 27 '20 at 17:35

Pablo C · Answer 2 · 2020-11-26T20:10:23.120

0

Use itertools.combinations (details here). First let's define some functions:

def difference(sublist1, sublist2):
    return abs(sum(sublist1) - sum(sublist2))

def complement(sublist, my_list):
    complement = my_list[:]
    for x in sublist:
        complement.remove(x)
    return complement

The function difference calculates the "distance" between lists, i.e, how similar the sums of the two lists are. complement returns the elements of my_list that are not in sublist.

Finally, what you are looking for:

def divide(my_list):
    lower_difference = sum(my_list) + 1
    for i in range(1, int(len(my_list)/2)+1):
        for partition in combinations(my_list, i):
            partition = list(partition)
            remainder = complement(partition, my_list)

            diff = difference(partition, remainder)
            if diff < lower_difference:
                lower_difference = diff
                solution = [partition, remainder]

    return solution

test1 = [4,1,8,6]
print(divide(test1)) #[[4, 6], [1, 8]]

test2 = [5,3,2,2,2,1]
print(divide(test2)) #[[5, 3], [2, 2, 2, 1]]

Basically, it tries with every possible division of sublists and returns the one with the minimum "distance".

If you want to make it a a little bit faster you could return the first combination whose difference is 0.

edited Nov 26 '20 at 20:10

answered Nov 26 '20 at 19:47

Pablo C

4,661
2
8
24

It almost works, but fails to return a solution for lists of size 2 – fdermishin Nov 26 '20 at 19:57
@user13044086 It works in my machine. Maybe a "versions" issue (?) – Pablo C Nov 26 '20 at 19:59
I've noticed that it happens if there is a zero in the list – fdermishin Nov 26 '20 at 20:02
@user13044086 size 2 with a zero in the list? or they both fail separately? – Pablo C Nov 26 '20 at 20:04
1

`solution` doesn't get assigned for list [0, 2]. You can fix it by replacing comparison by `diff <= lower_difference` – fdermishin Nov 26 '20 at 20:05
1

@user13044086 thank you! the problem comes from the initial value of `lower_difference` maybe there is a "smartest" initial value – Pablo C Nov 26 '20 at 20:11

gph · Answer 3 · 2020-11-26T19:03:04.263

-1

I think what you're looking for is a hill climbing algorithm. I'm not sure this will cover all cases but at least works for your example. I'll update this if I think of a counter example or something.

Let's call your list of numbers vals.

vals.sort(reverse=true)
a,b=[],[]
for v in vals:
  if sum(a)<sum(b):
    a.append(v)
  else: 
    b.append(v)

edited Nov 26 '20 at 19:03

answered Nov 26 '20 at 18:57

gph

1,045
8
25

It doesn't split list [10, 11, 14, 16, 19] into two equal halves by sum, but returns [16, 14], [19, 11, 10] instead – fdermishin Nov 26 '20 at 19:50
What's the right answer for that combo? I was thinking it might be a DP problem. – gph Nov 26 '20 at 22:39
It should be [10, 11, 14], [16, 19]. This arrangement seems to be the worst case scenario for this solution. A simpler case is [2, 2, 2, 3, 3], which is similar. In the final iteration sum(a)==sum(b), and it the smallest element is 2, which is then added to one of the arrays, making them unbalanced. An interesting property of this solution is that sums of the parts can't differ more than the smallest element. The problem can be solved using dynamic programming, but only in the case when magnitudes of elements are constrained, otherwise time complexity can become exponential. – fdermishin Nov 26 '20 at 22:57
I'm not following you re the magnitude of elements. The size of the input won't affect the complexity. Actual runtime, sure. – gph Nov 26 '20 at 23:07
If all elements are positive integers less than constant C, and list has size of n, then there exists DP solution with complexity O(C * n). But if elements are unconstrained, then it is Partition problem, which is NP-hard, and can't be solved in polynomial time. It is sometimes referred as pseudo-polynomial time dynamic programming – fdermishin Nov 26 '20 at 23:19
I don't think that constraint is correct. Constants are irrelevant for big-O notation. I think we are interpreting the question differently. – gph Nov 26 '20 at 23:26
I should have called it input parameter `m` instead of the constant. You can find detailed explanation of the algorithm here: https://stackoverflow.com/a/3421173/13044086 – fdermishin Nov 26 '20 at 23:57

Splitting list into 2 parts, as equal to sum as possible

3 Answers3