[Solved] Python split a list into N chunks with approximately equal sums [closed]

by


This is algorithmic approach (w/o any lib) and it’s faster too. Performance testing with 20-30 items list, it only took less than 1 second (earlier post will take 18-19 seconds!) It’s about 50-70 times faster.

It still has room to be improved, but for a reasonable size of list (40ish), it’s performant well enough (<1.5 seconds).

import time
def split_list(lst):
    '''split the list to 2 sublists with minimum difference '''
    
    iterations = range(2, len(lst)//2+1)

    totals = sum(lst)
    half = totals // 2; old_moves = {}
    
    half_lambda = lambda i: (abs((i)- half), i)

    for num in lst:
        left = lst[:]
        left.remove(num)
        old_moves[num] = left
    #print(f' old_moves: {old_moves} ')

    if iterations == []:         # float() ?
        ans = min(map(half_lambd, old_moves.keys()))
        return (ans[1], sum(old_moves[ans[1]]), old_moves[ans[1]])

    for n in iterations:
        new_moves = {}
        
        for total, roster in old_moves.items():
            for n in roster:
                left = roster[:]
                left.remove(n)
                new_total = total + n
                if new_total > half: continue
                new_moves[new_total] = left
        old_moves = new_moves

    ans = min(map(half_lambda, old_moves.keys()))
    another = list(set(lst) - set(old_moves[ans[1]]))
    #print(f' another: {another} ')
    return ans[1], sum(old_moves[ans[1]]), old_moves[ans[1]], another
                                            #old_moves[ans[0]])
lst  = [199, 139, 191, 140, 67, 437, 111, 122, 158, 123, 165, 138, 117, 132,
        990, 998, 888, 884, 332, 338]       # it only take 0.12 seconds

start = time.time()
print(split_list(lst))       # running the function
print(time.time() - start)   # in Python3.8 Aspire E15 machine (3.9 even faster)

1

solved Python split a list into N chunks with approximately equal sums [closed]