Split Array To Approximately Equal Chunks

How split array into two chunks, when sum of every chunk is approximately equal? >>> foo([10, 1, 1, 1]) [[10], [1, 1, 1]] >>> foo([2, 5, 9, 5, 1, 1]) [[2, 5], [9

Solution 1:

You can create your slicees with loop over your list then choose the proper pairs with min function with a proper key :

>>>deffind_min(l):...returnmin(((l[:i],l[i:]) for i inrange(len(l))),key=lambda x:abs((sum(x[0])-sum(x[1]))))

Demo :

>>>l=[10, 1, 1, 1]>>>find_min(l)
([10], [1, 1, 1])
>>>l=[9, 5, 5, 8, 2, 2, 18, 8, 3, 9, 4]>>>find_min(l)
([9, 5, 5, 8, 2, 2], [18, 8, 3, 9, 4])
>>>l=[19, 8, 9, 1, 14, 1, 16, 4, 15, 5]>>>find_min(l)
([19, 8, 9, 1, 14], [1, 16, 4, 15, 5])

Solution 2:

Something like that:

deffoo(lst):
    total_sum = sum(lst)
    i = 1while sum(lst[:i]) < total_sum / 2:  # iterate over the list slices until we hit the "middle" if sum(lst[:i+1]) >= total_sum / 2:  # also make sure that we won't go furtherbreak

        i += 1return [lst[:i], lst[i:]]

Testing:

[[10], [1, 1, 1]]                         # 10 + 3[[2, 5], [9, 5, 1, 1]]                    # 7 + 16[[9, 5, 5, 8, 2, 2], [18, 8, 3, 9, 4]]    # 31 + 42[[17, 15, 2, 18, 7], [20, 3, 20, 12, 7]]  # 59 + 62[[19, 8, 9, 1], [14, 1, 16, 4, 15, 5]]    # 37 + 55

Solution 3:

Assuming that the optimal split is obtained when the list is partitioned at the point where the cumulative sum of the list is as close as possible to half the sum of the whole list:

import numpy as np

x = [19, 8, 9, 1, 14, 1, 16, 4, 15, 5]
csum = np.cumsum(x)
ix = np.argmin(abs(csum-csum[-1]/2)) + 1
result = [x[:ix], x[ix:]]

Result:

[[19, 8, 9, 1, 14], [1, 16, 4, 15, 5]]

Solution 4:

from itertools import combinations
from collections import Counter


defmost_equal_pairs(seq, n=None):
    seq_mapping = dict(enumerate(seq))

    iflen(seq_mapping) < 2:
        raise ValueError()
    iflen(seq_mapping) == 2:
        first, second = seq_mapping.values()
        yield [first], [second], abs(first - second)
        return

    ids = set(seq_mapping)

    defget_chunk_by_ids(ids):
        return [seq_mapping[i] for i in ids]

    defget_chunk_sum_by_ids(ids):
        returnsum(get_chunk_by_ids(ids))

    pairs = Counter()

    for comb_len inrange(1, len(ids) - 1):
        for first_comb in combinations(ids, comb_len):
            second_comb = tuple(ids - set(first_comb))
            first_sum = get_chunk_sum_by_ids(first_comb)
            second_sum = get_chunk_sum_by_ids(second_comb)
            diff = abs(first_sum - second_sum)
            pairs[(first_comb, second_comb)] = -diff

    for (first_comb_ids, second_comb_ids), diff in pairs.most_common(n):
        first_comb = get_chunk_by_ids(first_comb_ids)
        second_comb = get_chunk_by_ids(second_comb_ids)
        yield first_comb, second_comb, abs(diff)


deftest(seq):
    pairs = list(most_equal_pairs(seq))
    diff_seq = []

    for first, second, diff in pairs:
        assertabs(sum(first) - sum(second)) == abs(diff)
        diff_seq.append(diff)

    asserttuple(sorted(diff_seq)) == tuple(diff_seq)
    best_pair = pairs[0]
    first, second, diff = best_pair
    return first, second, sum(first), sum(second), diff

result

>>> test([10, 1, 1, 1])
([10], [1, 1, 1], 10, 3, 7)

>>> test([2, 5, 9, 5, 1, 1])
([2, 9, 1], [5, 5, 1], 12, 11, 1)

>>> test([9, 5, 5, 8, 2, 2, 18, 8, 3, 9, 4])
([5, 8, 2, 2, 8, 3, 9], [9, 5, 4, 18], 37, 36, 1)

>>> test([17, 15, 2, 18, 7, 20, 3, 20, 12, 7])
([18, 3, 20, 12, 7], [17, 15, 2, 7, 20], 60, 61, 1)

>>> test([19, 8, 9, 1, 14, 1, 16, 4, 15, 5])
([19, 9, 14, 4], [8, 1, 1, 16, 15, 5], 46, 46, 0)

Solution 5:

Here is my solution:

defsum(*args):
    total = 0iflen(args) > 0:
        for i in args:
            for element in i:
                total += element
    return total

deffoo(Input):
    size = len(Input)
    checkLeftCross = 0
    previousLeft = 0
    previousRight = 0
    currentLeft = 0
    currentRight = 0
    targetIndex = 0for i inrange(size):
        currentLeft = sum(Input[0:i])
        currentRight = sum(Input[i:size])
        if currentLeft >= currentRight:
            targetIndex = i
            breakelse:
            previousLeft = currentLeft
            previousRight = currentRight

    diffPrev = previousRight - previousLeft
    diffCurr = currentLeft - currentRight

    if diffPrev > diffCurr:
        return Input[0:targetIndex], Input[targetIndex:size]
    else:
        return Input[0:targetIndex-1], Input[targetIndex-1:size]

defmain():
    print foo([2, 5, 9, 5, 1, 1])
    print foo([10,1,1,1])
    print foo([9, 5, 5, 8, 2, 2, 18, 8, 3, 9, 4])
    print foo([17, 15, 2, 18, 7, 20, 3, 20, 12, 7])
    print foo([19, 8, 9, 1, 14, 1, 16, 4, 15, 5])

if __name__ == "__main__":
    main()

Explanation:

1. I have used a function sum to return sum of all elements of list.
2. funciton foo to return 2 lists after being split after checking if current split was better or worse than previous split, based on difference between 2 successive sums.

Output:

([2, 5], [9, 5, 1, 1])
([10], [1, 1, 1])
([9, 5, 5, 8, 2, 2], [18, 8, 3, 9, 4])
([17, 15, 2, 18, 7], [20, 3, 20, 12, 7])
([19, 8, 9, 1, 14], [1, 16, 4, 15, 5])