Разделить массив примерно равными кусками

Что-то вроде того:

 def foo(lst): total_sum = sum(lst) i = 1 while 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 further break i += 1 return [lst[:i], lst[i:]] 

Тестирование:

 [[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 

Вы можете создавать свои срезы с помощью цикла над вашим списком, а затем выбирать правильные пары с помощью функции min с помощью соответствующего ключа:

 >>> def find_min(l): ... return min(((l[:i],l[i:]) for i in range(len(l))),key=lambda x:abs((sum(x[0])-sum(x[1])))) 

Демо:

 >>> 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]) 

Вот мое решение:

 def sum(*args): total = 0 if len(args) > 0: for i in args: for element in i: total += element return total def foo(Input): size = len(Input) checkLeftCross = 0 previousLeft = 0 previousRight = 0 currentLeft = 0 currentRight = 0 targetIndex = 0 for i in range(size): currentLeft = sum(Input[0:i]) currentRight = sum(Input[i:size]) if currentLeft >= currentRight: targetIndex = i break else: 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] def main(): 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() 

Объяснение:

1. Я использовал функцию sum для возврата суммы всех элементов списка.
2. funciton foo возвращает 2 списка после разделения после проверки того, был ли текущий раскол лучше или хуже предыдущего раскола, в зависимости от разницы между двумя последовательными суммами.

Вывод:

 ([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]) 

Предполагая, что оптимальное расщепление получается, когда список разбит на разделы, где сумма суммарного количества списка максимально приближена к половине суммы всего списка:

 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:]] 

Результат:

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

 from itertools import combinations from collections import Counter def most_equal_pairs(seq, n=None): seq_mapping = dict(enumerate(seq)) if len(seq_mapping) < 2: raise ValueError() if len(seq_mapping) == 2: first, second = seq_mapping.values() yield [first], [second], abs(first - second) return ids = set(seq_mapping) def get_chunk_by_ids(ids): return [seq_mapping[i] for i in ids] def get_chunk_sum_by_ids(ids): return sum(get_chunk_by_ids(ids)) pairs = Counter() for comb_len in range(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) def test(seq): pairs = list(most_equal_pairs(seq)) diff_seq = [] for first, second, diff in pairs: assert abs(sum(first) - sum(second)) == abs(diff) diff_seq.append(diff) assert tuple(sorted(diff_seq)) == tuple(diff_seq) best_pair = pairs[0] first, second, diff = best_pair return first, second, sum(first), sum(second), diff 

результат

 >>> 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)