Dividir una lista de números en n partes, de manera que las partes tengan (cerca de) sums iguales y conserven el orden original

Este no es el problema de partición estándar, ya que necesito mantener el orden de los elementos en la lista.

Así por ejemplo si tengo una lista

[1, 6, 2, 3, 4, 1, 7, 6, 4] 

y quiero dos trozos, entonces la división debería dar

 [[1, 6, 2, 3, 4, 1], [7, 6, 4]] 

por una sum de 17 en cada lado. Por tres trozos el resultado sería

 [[1, 6, 2, 3], [4, 1, 7], [6, 4]] 

Para sums de 12, 12 y 10.

Editar para explicación adicional

Actualmente divido la sum con la cantidad de partes y la uso como objective, luego itero hasta que me acerque a ese objective. El problema es que ciertos conjuntos de datos pueden desordenar el algoritmo, por ejemplo, tratando de dividir lo siguiente en 3:

 [95, 15, 75, 25, 85, 5] 

La sum es 300, el objective es 100. La primera parte se sumría a 95, la segunda se sumría a 90, la tercera se sumría a 110 y 5 sería “sobrante”. Anexarlo donde se supone que debe estar sería 95, 90, 115, donde una solución más “razonable” sería 110, 100, 90.

edición final

Fondo:

Tengo una lista que contiene texto (letras de canciones) de diferentes alturas, y quiero dividir el texto en un número arbitrario de columnas. Actualmente calculo una altura objective basada en la altura total de todas las líneas, pero obviamente esta es una subestimación constante, lo que en algunos casos da como resultado una solución subóptima (la última columna es significativamente más alta).

Este enfoque define los límites de partición que dividen la matriz en aproximadamente el mismo número de elementos, y luego busca repetidamente mejores particiones hasta que no pueda encontrar más. Se diferencia de la mayoría de las otras soluciones publicadas en que busca una solución óptima al probar varias particiones diferentes. Las otras soluciones intentan crear una buena partición en una sola pasada a través de la matriz, pero no puedo pensar en un algoritmo de una sola pasada que esté garantizado como óptimo.

El código aquí es una implementación eficiente de este algoritmo, pero puede ser difícil de entender, por lo que al final se incluye una versión más legible como una adición.

 def partition_list(a, k): if k <= 1: return [a] if k >= len(a): return [[x] for x in a] partition_between = [(i+1)*len(a)/k for i in range(k-1)] average_height = float(sum(a))/k best_score = None best_partitions = None count = 0 while True: starts = [0]+partition_between ends = partition_between+[len(a)] partitions = [a[starts[i]:ends[i]] for i in range(k)] heights = map(sum, partitions) abs_height_diffs = map(lambda x: abs(average_height - x), heights) worst_partition_index = abs_height_diffs.index(max(abs_height_diffs)) worst_height_diff = average_height - heights[worst_partition_index] if best_score is None or abs(worst_height_diff) < best_score: best_score = abs(worst_height_diff) best_partitions = partitions no_improvements_count = 0 else: no_improvements_count += 1 if worst_height_diff == 0 or no_improvements_count > 5 or count > 100: return best_partitions count += 1 move = -1 if worst_height_diff < 0 else 1 bound_to_move = 0 if worst_partition_index == 0\ else k-2 if worst_partition_index == k-1\ else worst_partition_index-1 if (worst_height_diff < 0) ^ (heights[worst_partition_index-1] > heights[worst_partition_index+1])\ else worst_partition_index direction = -1 if bound_to_move < worst_partition_index else 1 partition_between[bound_to_move] += move * direction def print_best_partition(a, k): print 'Partitioning {0} into {1} partitions'.format(a, k) p = partition_list(a, k) print 'The best partitioning is {0}\n With heights {1}\n'.format(p, map(sum, p)) a = [1, 6, 2, 3, 4, 1, 7, 6, 4] print_best_partition(a, 1) print_best_partition(a, 2) print_best_partition(a, 3) print_best_partition(a, 4) b = [1, 10, 10, 1] print_best_partition(b, 2) import random c = [random.randint(0,20) for x in range(100)] print_best_partition(c, 10) d = [95, 15, 75, 25, 85, 5] print_best_partition(d, 3) 

Puede haber algunas modificaciones que hacer dependiendo de lo que esté haciendo con esto. Por ejemplo, para determinar si se ha encontrado la mejor partición, este algoritmo se detiene cuando no hay diferencia de altura entre las particiones, no encuentra nada mejor que lo mejor que se ha visto durante más de 5 iteraciones seguidas, o después de 100 Total de iteraciones como punto de parada de captura de todo. Es posible que deba ajustar esas constantes o usar un esquema diferente. Si sus alturas forman un complejo outlook de valores, saber cuándo detenerse puede meterse en los problemas clásicos de tratar de escapar de los máximos locales y cosas así.

Salida

 Partitioning [1, 6, 2, 3, 4, 1, 7, 6, 4] into 1 partitions The best partitioning is [[1, 6, 2, 3, 4, 1, 7, 6, 4]] With heights [34] Partitioning [1, 6, 2, 3, 4, 1, 7, 6, 4] into 2 partitions The best partitioning is [[1, 6, 2, 3, 4, 1], [7, 6, 4]] With heights [17, 17] Partitioning [1, 6, 2, 3, 4, 1, 7, 6, 4] into 3 partitions The best partitioning is [[1, 6, 2, 3], [4, 1, 7], [6, 4]] With heights [12, 12, 10] Partitioning [1, 6, 2, 3, 4, 1, 7, 6, 4] into 4 partitions The best partitioning is [[1, 6], [2, 3, 4], [1, 7], [6, 4]] With heights [7, 9, 8, 10] Partitioning [1, 10, 10, 1] into 2 partitions The best partitioning is [[1, 10], [10, 1]] With heights [11, 11] Partitioning [7, 17, 17, 1, 8, 8, 12, 0, 10, 20, 17, 13, 12, 4, 1, 1, 7, 11, 7, 13, 9, 12, 3, 18, 9, 6, 7, 19, 20, 17, 7, 4, 3, 16, 20, 6, 7, 12, 16, 3, 6, 12, 9, 4, 3, 2, 18, 1, 16, 14, 17, 7, 0, 14, 13, 3, 5, 3, 1, 5, 5, 13, 16, 0, 16, 7, 3, 8, 1, 20, 16, 11, 15, 3, 10, 10, 2, 0, 12, 12, 0, 18, 20, 3, 10, 9, 13, 12, 15, 6, 14, 16, 6, 12, 9, 9, 16, 14, 19, 1] into 10 partitions The best partitioning is [[7, 17, 17, 1, 8, 8, 12, 0, 10, 20], [17, 13, 12, 4, 1, 1, 7, 11, 7, 13, 9], [12, 3, 18, 9, 6, 7, 19, 20], [17, 7, 4, 3, 16, 20, 6, 7, 12], [16, 3, 6, 12, 9, 4, 3, 2, 18, 1, 16], [14, 17, 7, 0, 14, 13, 3, 5, 3, 1, 5, 5], [13, 16, 0, 16, 7, 3, 8, 1, 20, 16], [11, 15, 3, 10, 10, 2, 0, 12, 12, 0, 18], [20, 3, 10, 9, 13, 12, 15, 6, 14], [16, 6, 12, 9, 9, 16, 14, 19, 1]] With heights [100, 95, 94, 92, 90, 87, 100, 93, 102, 102] Partitioning [95, 15, 75, 25, 85, 5] into 3 partitions The best partitioning is [[95, 15], [75, 25], [85, 5]] With heights [110, 100, 90] 

Editar

Se agregó el nuevo caso de prueba, [95, 15, 75, 25, 85, 5], que este método maneja correctamente.

Apéndice

Esta versión del algoritmo es más fácil de leer y comprender, pero es un poco más larga debido a que se aprovecha menos las funciones incorporadas de Python. Sin embargo, parece ejecutarse en un tiempo comparable o incluso un poco más rápido.

 #partition list a into k partitions def partition_list(a, k): #check degenerate conditions if k <= 1: return [a] if k >= len(a): return [[x] for x in a] #create a list of indexes to partition between, using the index on the #left of the partition to indicate where to partition #to start, roughly partition the array into equal groups of len(a)/k (note #that the last group may be a different size) partition_between = [] for i in range(k-1): partition_between.append((i+1)*len(a)/k) #the ideal size for all partitions is the total height of the list divided #by the number of paritions average_height = float(sum(a))/k best_score = None best_partitions = None count = 0 no_improvements_count = 0 #loop over possible partitionings while True: #partition the list partitions = [] index = 0 for div in partition_between: #create partitions based on partition_between partitions.append(a[index:div]) index = div #append the last partition, which runs from the last partition divider #to the end of the list partitions.append(a[index:]) #evaluate the partitioning worst_height_diff = 0 worst_partition_index = -1 for p in partitions: #compare the partition height to the ideal partition height height_diff = average_height - sum(p) #if it's the worst partition we've seen, update the variables that #track that if abs(height_diff) > abs(worst_height_diff): worst_height_diff = height_diff worst_partition_index = partitions.index(p) #if the worst partition from this run is still better than anything #we saw in previous iterations, update our best-ever variables if best_score is None or abs(worst_height_diff) < best_score: best_score = abs(worst_height_diff) best_partitions = partitions no_improvements_count = 0 else: no_improvements_count += 1 #decide if we're done: if all our partition heights are ideal, or if #we haven't seen improvement in >5 iterations, or we've tried 100 #different partitionings #the criteria to exit are important for getting a good result with #complex data, and changing them is a good way to experiment with getting #improved results if worst_height_diff == 0 or no_improvements_count > 5 or count > 100: return best_partitions count += 1 #adjust the partitioning of the worst partition to move it closer to the #ideal size. the overall goal is to take the worst partition and adjust #its size to try and make its height closer to the ideal. generally, if #the worst partition is too big, we want to shrink the worst partition #by moving one of its ends into the smaller of the two neighboring #partitions. if the worst partition is too small, we want to grow the #partition by expanding the partition towards the larger of the two #neighboring partitions if worst_partition_index == 0: #the worst partition is the first one if worst_height_diff < 0: partition_between[0] -= 1 #partition too big, so make it smaller else: partition_between[0] += 1 #partition too small, so make it bigger elif worst_partition_index == len(partitions)-1: #the worst partition is the last one if worst_height_diff < 0: partition_between[-1] += 1 #partition too small, so make it bigger else: partition_between[-1] -= 1 #partition too big, so make it smaller else: #the worst partition is in the middle somewhere left_bound = worst_partition_index - 1 #the divider before the partition right_bound = worst_partition_index #the divider after the partition if worst_height_diff < 0: #partition too big, so make it smaller if sum(partitions[worst_partition_index-1]) > sum(partitions[worst_partition_index+1]): #the partition on the left is bigger than the one on the right, so make the one on the right bigger partition_between[right_bound] -= 1 else: #the partition on the left is smaller than the one on the right, so make the one on the left bigger partition_between[left_bound] += 1 else: #partition too small, make it bigger if sum(partitions[worst_partition_index-1]) > sum(partitions[worst_partition_index+1]): #the partition on the left is bigger than the one on the right, so make the one on the left smaller partition_between[left_bound] -= 1 else: #the partition on the left is smaller than the one on the right, so make the one on the right smaller partition_between[right_bound] += 1 def print_best_partition(a, k): #simple function to partition a list and print info print ' Partitioning {0} into {1} partitions'.format(a, k) p = partition_list(a, k) print ' The best partitioning is {0}\n With heights {1}\n'.format(p, map(sum, p)) #tests a = [1, 6, 2, 3, 4, 1, 7, 6, 4] print_best_partition(a, 1) print_best_partition(a, 2) print_best_partition(a, 3) print_best_partition(a, 4) print_best_partition(a, 5) b = [1, 10, 10, 1] print_best_partition(b, 2) import random c = [random.randint(0,20) for x in range(100)] print_best_partition(c, 10) d = [95, 15, 75, 25, 85, 5] print_best_partition(d, 3) 

Aquí está el mejor algoritmo O (n) codicioso que tengo por ahora. La idea es agregar codiciosamente elementos de la lista a un trozo hasta que la sum para el trozo actual exceda la sum esperada promedio para un trozo en ese punto. La sum media esperada se actualiza constantemente. Esta solución no es perfecta, pero como dije, es O (n) y no funcionó mal con mis pruebas. Estoy ansioso por escuchar comentarios y sugerencias para mejorar.

Dejé mis declaraciones de impresión de depuración en el código para proporcionar algo de documentación. Siéntase libre de comentarlos para ver qué sucede en cada paso.

CÓDIGO

 def split_list(lst, chunks): #print(lst) #print() chunks_yielded = 0 total_sum = sum(lst) avg_sum = total_sum/float(chunks) chunk = [] chunksum = 0 sum_of_seen = 0 for i, item in enumerate(lst): #print('start of loop! chunk: {}, index: {}, item: {}, chunksum: {}'.format(chunk, i, item, chunksum)) if chunks - chunks_yielded == 1: #print('must yield the rest of the list! chunks_yielded: {}'.format(chunks_yielded)) yield chunk + lst[i:] raise StopIteration to_yield = chunks - chunks_yielded chunks_left = len(lst) - i if to_yield > chunks_left: #print('must yield remaining list in single item chunks! to_yield: {}, chunks_left: {}'.format(to_yield, chunks_left)) if chunk: yield chunk yield from ([x] for x in lst[i:]) raise StopIteration sum_of_seen += item if chunksum < avg_sum: #print('appending {} to chunk {}'.format(item, chunk)) chunk.append(item) chunksum += item else: #print('yielding chunk {}'.format(chunk)) yield chunk # update average expected sum, because the last yielded chunk was probably not perfect: avg_sum = (total_sum - sum_of_seen)/(to_yield - 1) chunks_yielded += 1 chunksum = item chunk = [item] 

CÓDIGO DE PRUEBA

 import random lst = [1, 6, 2, 3, 4, 1, 7, 6, 4] #lst = [random.choice(range(1,101)) for _ in range(100)] chunks = 3 print('list: {}, avg sum: {}, chunks: {}\n'.format(lst, sum(lst)/float(chunks), chunks)) for chunk in split_list(lst, chunks): print('chunk: {}, sum: {}'.format(chunk, sum(chunk))) 

PRUEBAS con tu lista:

 list: [1, 6, 2, 3, 4, 1, 7, 6, 4], avg sum: 17.0, chunks: 2 chunk: [1, 6, 2, 3, 4, 1], sum: 17 chunk: [7, 6, 4], sum: 17 --- list: [1, 6, 2, 3, 4, 1, 7, 6, 4], avg sum: 11.33, chunks: 3 chunk: [1, 6, 2, 3], sum: 12 chunk: [4, 1, 7], sum: 12 chunk: [6, 4], sum: 10 --- list: [1, 6, 2, 3, 4, 1, 7, 6, 4], avg sum: 8.5, chunks: 4 chunk: [1, 6, 2], sum: 9 chunk: [3, 4, 1], sum: 8 chunk: [7], sum: 7 chunk: [6, 4], sum: 10 --- list: [1, 6, 2, 3, 4, 1, 7, 6, 4], avg sum: 6.8, chunks: 5 chunk: [1, 6], sum: 7 chunk: [2, 3, 4], sum: 9 chunk: [1, 7], sum: 8 chunk: [6], sum: 6 chunk: [4], sum: 4 

PRUEBAS con listas aleatorias de longitud 100 y elementos de 1 a 100 (impresión de la lista aleatoria omitida):

 avg sum: 2776.0, chunks: 2 chunk: [25, 8, 71, 39, 5, 69, 29, 64, 31, 2, 90, 73, 72, 58, 52, 19, 64, 34, 16, 8, 16, 89, 70, 67, 63, 36, 9, 87, 38, 33, 22, 73, 66, 93, 46, 48, 65, 55, 81, 92, 69, 94, 43, 68, 98, 70, 28, 99, 92, 69, 24, 74], sum: 2806 chunk: [55, 55, 64, 93, 97, 53, 85, 100, 66, 61, 5, 98, 43, 74, 99, 56, 96, 74, 63, 6, 89, 82, 8, 25, 36, 68, 89, 84, 10, 46, 95, 41, 54, 39, 21, 24, 8, 82, 72, 51, 31, 48, 33, 77, 17, 69, 50, 54], sum: 2746 --- avg sum: 1047.6, chunks: 5 chunk: [19, 76, 96, 78, 12, 33, 94, 10, 38, 87, 44, 76, 28, 18, 26, 29, 44, 98, 44, 32, 80], sum: 1062 chunk: [48, 70, 42, 85, 87, 55, 44, 11, 50, 48, 47, 50, 1, 17, 93, 78, 25, 10, 89, 57, 85], sum: 1092 chunk: [30, 83, 99, 62, 48, 66, 65, 98, 94, 54, 14, 97, 58, 53, 3, 98], sum: 1022 chunk: [80, 34, 63, 20, 27, 36, 98, 97, 7, 6, 9, 65, 91, 93, 2, 27, 83, 35, 65, 17, 26, 41], sum: 1022 chunk: [80, 80, 42, 32, 44, 42, 94, 31, 50, 23, 34, 84, 47, 10, 54, 59, 72, 80, 6, 76], sum: 1040 --- avg sum: 474.6, chunks: 10 chunk: [4, 41, 47, 41, 32, 51, 81, 5, 3, 37, 40, 26, 10, 70], sum: 488 chunk: [54, 8, 91, 42, 35, 80, 13, 84, 14, 23, 59], sum: 503 chunk: [39, 4, 38, 40, 88, 69, 10, 19, 28, 97, 81], sum: 513 chunk: [19, 55, 21, 63, 99, 93, 39, 47, 29], sum: 465 chunk: [65, 88, 12, 94, 7, 47, 14, 55, 28, 9, 98], sum: 517 chunk: [19, 1, 98, 84, 92, 99, 11, 53], sum: 457 chunk: [85, 79, 69, 78, 44, 6, 19, 53], sum: 433 chunk: [59, 20, 64, 55, 2, 65, 44, 90, 37, 26], sum: 462 chunk: [78, 66, 32, 76, 59, 47, 82], sum: 440 chunk: [34, 56, 66, 27, 1, 100, 16, 5, 97, 33, 33], sum: 468 --- avg sum: 182.48, chunks: 25 chunk: [55, 6, 16, 42, 85], sum: 204 chunk: [30, 68, 3, 94], sum: 195 chunk: [68, 96, 23], sum: 187 chunk: [69, 19, 12, 97], sum: 197 chunk: [59, 88, 49], sum: 196 chunk: [1, 16, 13, 12, 61, 77], sum: 180 chunk: [49, 75, 44, 43], sum: 211 chunk: [34, 86, 9, 55], sum: 184 chunk: [25, 82, 12, 93], sum: 212 chunk: [32, 74, 53, 31], sum: 190 chunk: [13, 15, 26, 31, 35, 3, 14, 71], sum: 208 chunk: [81, 92], sum: 173 chunk: [94, 21, 34, 71], sum: 220 chunk: [1, 55, 70, 3, 92], sum: 221 chunk: [38, 59, 56, 57], sum: 210 chunk: [7, 20, 10, 81, 100], sum: 218 chunk: [5, 71, 19, 8, 82], sum: 185 chunk: [95, 14, 72], sum: 181 chunk: [2, 8, 4, 47, 75, 17], sum: 153 chunk: [56, 69, 42], sum: 167 chunk: [75, 45], sum: 120 chunk: [68, 60], sum: 128 chunk: [29, 25, 62, 3, 50], sum: 169 chunk: [54, 63], sum: 117 chunk: [57, 37, 42], sum: 136 

Como puede ver, como era de esperar, se agrava cuanto más fragmentos desea generar. Espero haber podido ayudar un poco.

edición: el yield from syntax requiere Python 3.3 o más reciente, si está utilizando una versión anterior, simplemente convierta la statement en un bucle normal para.

Creo que un buen enfoque sería ordenar la lista de entrada. Luego agrega el más pequeño y el más grande a una lista. El segundo más pequeño y el segundo más grande a la siguiente lista y así sucesivamente, hasta que todos los elementos se agreguen a la lista.

 def divide_list(A): A.sort() l = 0 r = len(A) - 1 l1,l2= [],[] i = 0 while l < r: ends = [A[l], A[r]] if i %2 ==0: l1.extend(ends) else: l2.extend(ends) i +=1 l +=1 r -=1 if r == l: smaller = l1 if sum(l1) < sum(l2) else l2 smaller.append(A[r]) return l1, l2 myList = [1, 6, 2, 3, 4, 1, 7, 6, 4] print divide_list(myList) myList = [1,10,10,1] print divide_list(myList) 

Salida

 ([1, 7, 2, 6], [1, 6, 3, 4, 4]) ([1, 10], [1, 10]) 

Esto llegará un poco tarde, pero se me ocurrió una función que hace lo que necesita, toma un segundo parámetro que le dice cómo debe dividir la lista

 import math my_list = [1, 6, 2, 3, 4, 1, 7, 6, 4] def partition(my_list, split): solution = [] total = sum(my_list) div = total / split div = math.ceil(div) criteria = [div] * (total // div) criteria.append(total - sum(criteria)) if sum(criteria) != total else criteria temp = [] pivot = 0 for crit in criteria: for count in range(len(my_list) + 1): if sum(my_list[pivot:count]) == crit: solution.append(my_list[pivot:count]) pivot = count break return solution print(partition(my_list, 2)) # Outputs [[1, 6, 2, 3, 4, 1], [7, 6, 4]] print(partition(my_list, 3)) # Outputs [[1, 6, 2, 3], [4, 1, 7], [6, 4]] 

fallaría para 4 divisiones, porque obviamente en su pregunta indicó que desea mantener el orden

 4 divisions = [9, 9, 9, 7] 

y tu secuencia no puede coincidir con eso

Aquí hay un código que devuelve 2-ples de índices de corte para cada sublista.

 weights = [1, 6, 2, 3, 4, 1, 7, 6, 4] def balance_partitions(weights:list, n:int=2) -> tuple: if n < 1: raise ValueError("Parameter 'n' must be 2+") target = sum(weights) // n results = [] cost = 0 start = 0 for i, w in enumerate(weights): delta = target - cost cost += w if cost >= target: if i == 0 or cost - target <= delta: results.append( (start, i+1) ) start = i+1 elif cost - target > delta: # Better if we didn't include this one. results.append( (start, i) ) start = i cost -= target if len(results) == n-1: results.append( (start, len(weights)) ) break return tuple(results) def print_parts(w, n): result = balance_partitions(w, n) print("Suggested partition indices: ", result) for t in result: start,end = t sublist = w[start:end] print(" - ", sublist, "(sum: {})".format(sum(sublist))) print(weights, '=', sum(weights)) for i in range(2, len(weights)+1): print_parts(weights, i) 

La salida es:

 [1, 6, 2, 3, 4, 1, 7, 6, 4] = 34 Suggested partition indices: ((0, 6), (6, 9)) - [1, 6, 2, 3, 4, 1] (sum: 17) - [7, 6, 4] (sum: 17) Suggested partition indices: ((0, 4), (4, 7), (7, 9)) - [1, 6, 2, 3] (sum: 12) - [4, 1, 7] (sum: 12) - [6, 4] (sum: 10) Suggested partition indices: ((0, 3), (3, 5), (5, 7), (7, 9)) - [1, 6, 2] (sum: 9) - [3, 4] (sum: 7) - [1, 7] (sum: 8) - [6, 4] (sum: 10) Suggested partition indices: ((0, 2), (2, 4), (4, 6), (6, 7), (7, 9)) - [1, 6] (sum: 7) - [2, 3] (sum: 5) - [4, 1] (sum: 5) - [7] (sum: 7) - [6, 4] (sum: 10) Suggested partition indices: ((0, 2), (2, 3), (3, 5), (5, 6), (6, 7), (7, 9)) - [1, 6] (sum: 7) - [2] (sum: 2) - [3, 4] (sum: 7) - [1] (sum: 1) - [7] (sum: 7) - [6, 4] (sum: 10) Suggested partition indices: ((0, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 9)) - [1, 6] (sum: 7) - [2] (sum: 2) - [3] (sum: 3) - [4] (sum: 4) - [1] (sum: 1) - [7] (sum: 7) - [6, 4] (sum: 10) Suggested partition indices: ((0, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)) - [1, 6] (sum: 7) - [2] (sum: 2) - [3] (sum: 3) - [4] (sum: 4) - [1] (sum: 1) - [7] (sum: 7) - [6] (sum: 6) - [4] (sum: 4) Suggested partition indices: ((0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)) - [1] (sum: 1) - [6] (sum: 6) - [2] (sum: 2) - [3] (sum: 3) - [4] (sum: 4) - [1] (sum: 1) - [7] (sum: 7) - [6] (sum: 6) - [4] (sum: 4) 

Así es como podría atacar este problema en el caso de dos sublistas deseados. Probablemente no sea tan eficiente como podría ser, pero es un primer corte.

 def divide(l): total = sum(l) half = total / 2 l1 = [] l2 = [] for e in l: if half - e >= 0 or half > abs(half - e): l1.append(e) half -= e else: l2.append(e) return (l1, l2) 

Puedes verlo en acción aqui:

 (l1, l2) = divide([1, 6, 2, 3, 4, 1, 7, 6, 4]) print(l1) # [1, 6, 2, 3, 4, 1] print(l2) #[7, 6, 4] (l1, l2) = divide([1,1,10,10]) print(l1) # [1, 1, 10] print(l2) #[10] 

Te dejaré otros casos como ejercicio. 🙂

Manera simple y concisa usando numpy. Asumiendo

 import numpy.random as nr import numpy as np a = (nr.random(10000000)*1000).astype(int) 

Luego, asumiendo que necesita dividir la lista en p partes con sums aproximadamente iguales

 def equisum_partition(arr,p): ac = arr.cumsum() #sum of the entire array partsum = ac[-1]//p #generates the cumulative sums of each part cumpartsums = np.array(range(1,p))*partsum #finds the indices where the cumulative sums are sandwiched inds = np.searchsorted(ac,cumpartsums) #split into approximately equal-sum arrays parts = np.split(arr,inds) return parts 

Es importante destacar que esto se vectoriza:

 In [3]: %timeit parts = equisum_partition(a,20) 53.5 ms ± 962 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 

Podrías comprobar la calidad de la división,

 partsums = np.array([part.sum() for part in parts]).std() 

Las divisiones no son excelentes, pero sospecho que son óptimas dado que el orden no ha cambiado.