How to distribute the sum of several numbers similarly?

Question

Is there a way to distribute more similarly than the method below? I'm also curious about how to distribute it from more than one list. The list can contain only five numbers.

intList = []
for i in range(10):
    intList.append(random.randint(10,200))


listX = []
listY = []

intList.sort(reverse=True)

for i in range(len(intList)):
    if sum(listX) >= sum(listY):
        if len(listY) != 5:
            listY.append(intList[i])
        else:
            listX.append(intList[i])
    else:
        if len(listX) != 5:
            listX.append(intList[i])
        else:
            listY.append(intList[i])

print(f"listx = {listX} \nlisty = {listY}\n sum x = {sum(listX)}, y = {sum(listY)}")

Answer 1

You should sort the list of integers in descending order and then iterate through it, adding each number to the list with the smaller current sum, like the following:

import random

intList = []
for i in range(10):
    intList.append(random.randint(10, 200))

listX = []
listY = []

intList.sort(reverse=True)

sumX = 0
sumY = 0

for num in intList:
    if sumX <= sumY:
        listX.append(num)
        sumX += num
    else:
        listY.append(num)
        sumY += num

print(f"listx = {listX} \nlisty = {listY}\n sum x = {sumX}, y = {sumY}")

Edit

To ensure that both lists have exactly 5 elements and maintain balanced lengths, you can modify the algorithm to distribute the numbers based on the lengths of the lists. If one list has fewer than 5 elements, prioritize it adding numbers to that list until it reaches 5 elements.

Try this:

import random

intList = []
listX = []
listY = []

for i in range(10):
    num = random.randint(0, 5)
    intList.append(num)

intList.sort(reverse=True)

sumX = 0
sumY = 0

for num in intList:
    if len(listX) < 5:
        listX.append(num)
        sumX += num
    elif len(listY) < 5:
        listY.append(num)
        sumY += num
    elif sumX <= sumY:
        listX.append(num)
        sumX += num
    else:
        listY.append(num)
        sumY += num

print(f"listx = {listX} \nlisty = {listY}\n sum x = {sumX}, y = {sumY}")

Answer 2

One counter example to your solution is:

[8, 7, 5, 4, 4, 1]

Adding as you have done would give the subsets:

[8, 4, 4], [7, 5, 1]: difference of sums = 3

while the optimal solution is:

[8, 5, 4], [7, 4, 1]: difference of sums = 1

Thus, to solve this problem, you need to brute force generate all combinations of (n choose floor(n/2)) and find the one with the smallest difference. Here is a sample code:

comb = []
def getcomb(l, ind, k):
    if len(comb) == k:
        return [comb[:]]
    if ind == len(l):
        return []
    ret = getcomb(l, ind+1, k)
    comb.append(l[ind])
    ret += getcomb(l, ind+1, k)
    comb.pop()
    return ret

def get_best_split(l):
    lsm = sum(l)
    best = lsm
    a = []
    for i in getcomb(l, 0, len(l)//2):
        sm = sum(i)
        if abs(sm - (lsm - sm)) < best:
            best = abs(sm - (lsm - sm))
            a = i

    b = [x for x in l if x not in a]
    return best, a, b

print(get_best_split([8, 7, 5, 4, 4, 1])) 
# outputs (1, [7, 4, 4], [8, 5, 1])

EDIT:

If you don't care about the subsets themselves, then you can just generate all possible sums:

def getcomb(l, ind, k, val):
    if k == 0:
        return [val]
    if ind == len(l):
        return []
    return getcomb(l, ind+1, k, val) + getcomb(l, ind+1, k-1, val + l[ind]) 

def get_best_split(l):
    l = sorted(l, reverse=True)
    best = 1000000
    for i in getcomb(l, 0, len(l)//2, 0):
        best = min(best, abs(i - (sum(l) - i)))
    return best

EDIT 2: Another interesting thing to try out might be a modified knapsack solution, where you keep track of the set of the number of elements that can make each value. The complexity would be N^2 * sum(L), which is arguably better than N choose (N/2) depending on how large the average element in your list is:

def get_best_split_knapsack(l):
    sm = sum(l)
    dp = [[-1, set()] for _ in range(sm+1)]
    dp[0][0] = 1
    dp[0][1].add(0)

    best = sm 

    for i in l:
        for j in range(sm//2, i-1, -1):
            if dp[j-i][0] == 1:
                dp[j][0] = 1
                dp[j][1].update(k+1 for k in dp[j-i][1])
        
        for j in range(max(0,int(sm//2-best)), min(int(sm//2+best)+1, sm)):
            if dp[j][0] == 1 and len(l)//2 in dp[j][1]:
                best = min(best, abs(sm/2 - j))
        
    return int(2*best)