Split Array auf etwa gleich Chunks

Wie Split Array in zwei Chunks, wenn Summe von jedem Chunk ist etwa gleich?

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

5 Solutions collect form web for “Split Array auf etwa gleich Chunks”

So ähnlich:

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

Testen:

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

Sie können Ihre Slicees mit Loop über Ihre Liste erstellen und dann die richtigen Paare mit min Funktion mit einem richtigen Schlüssel auswählen:

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

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

Hier ist meine Lösung:

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

Erläuterung:

  1. Ich habe eine Funktion sum , um Summe aller Elemente der Liste zurückzugeben.
  2. Funciton foo, um 2 Listen zurückzugeben, nachdem sie aufgeteilt wurden, nachdem sie überprüft hatten, ob der aktuelle Split besser oder schlechter war als der vorherige Split, basierend auf dem Unterschied zwischen zwei aufeinanderfolgenden Summen.

Ausgabe:

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

Angenommen, der optimale Split wird erhalten, wenn die Liste an der Stelle partitioniert wird, an der die kumulative Summe der Liste so nahe wie möglich an der Hälfte der Summe der gesamten Liste liegt:

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

Ergebnis:

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

Ergebnis

 >>> 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) 
  • Überprüfen Sie, ob String in einem Pandas-Dataframe ist
  • So greifen Sie auf Variablen aus der über die Befehlszeile übergebenen Datei zu
  • Bekomme aktuelle URL aus Browser-Python
  • Wie kann ich das Bild eines Tkinter Label-Widgets aktualisieren?
  • Wie decode url zu Pfad in Python, Django
  • Verwenden von super () in einer Eigenschaft Setter-Methode, wenn die Verwendung der @ property Dekorator erhöht ein AttributeError
  • Kein Modul namens setuptools
  • Verketten ein angepasstes Format einer spärlichen Matrix X mit einem Zielfeld Y in Python
  • Wie benutzt man den User_passes_Test Dekorator in klassenbasierten Ansichten?
  • Pickle Queue Objekte in Python
  • Wie füge ich einen Funktionsaufruf zu einer Liste hinzu?
  • Python ist die beste Programmiersprache der Welt.