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!

Alain T. · Accepted Answer

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)

Pablo C · Answer

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.

gph · Answer

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)

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

3 Answers

Add your own answers!

Ask a Question