Finden einer Summe von X-Nummern innerhalb einer Liste (Python)

Question

Ich versuche, eine Kombination für eine Summe innerhalb einer Liste von ganzen Zahlen zu finden.

die Menge von Zahlen, die die Summe enthalten, die durch eine Variable begrenzt ist, so zum Beispiel in der Liste -

[5,2,3,9,1], würde ich die Summe von 10 finden möchte mit nur 2 Nummern.

so dass das Programm [9,1] ausdrucken würde.

Ich bin neu in Python, gibt es eine einfache Möglichkeit, es zu tun?

danke.

Answer 1

Die Brute-Force-Ansatz itertools.combinations:

In [6]: [pair for pair in itertools.combinations(li,2) if sum(pair) == 10] 
Out[6]: [(9, 1)] 

Dies gibt Ihnen alle Paare, die Summe bis 10. Diese superexponential in Laufzeit, also, wenn Sie Ihre Eingaben groß sind, werden Sie einen ausgeklügelten Algorithmus wollen.

Answer 2

from itertools import combinations 

l = [5,2,3,9,1] 

for var in combinations(l, 2): 
    if var[0] + var[1] == 10: 
     print var[0], var[1] 

Combinations schaffen alle möglichen Kombinationen von tuples von einem iterable Objekt (ein Objekt Sie Schleife kann über). Lassen Sie mich zeigen:

>>> [var for var in combinations([1,2,3,4,5], 2)] 
[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)] 
>>> [var for var in combinations([1,2,3,4,5], 3)] 
[(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)] 

Answer 3

ls = [5, 2, 3, 9, 1] 
sum = 10 

while ls: 
    num = ls.pop() 
    diff = sum - num 
    if diff in ls: 
     print([num, diff]) 

Answer 4

Just for Code Golf Zwecke, hier ist der collections.Counter Ansatz:

import collections 
integers_list = [5,2,3,9,1] 
integer_counts = collections.Counter(integers_list) 
for x in integers_list: 
    y = 10 - x 
    if (x != y and integer_counts[y]) or (x == y and integer_counts[y] > 1): 
     print (x, y) # Or, if building a new list, append instead of print 
     integer_counts.subtract((x, y)) 

collections.Counter wurde in 2.7 hinzugefügt. Für frühere Versionen müssen Sie stattdessen defaultdict verwenden. Es ist nicht viel komplexer.

Ich denke, das ist schwieriger zu lesen als die itertools.combinations Version @roippi geschrieben, aber es sollte deutlich schneller sein, wenn die Liste der ganzen Zahlen groß ist. Normalerweise schätze ich die menschliche Zeit, die den Code liest, über die Zeit, in der sie ausgeführt wird, aber welche Überlegung gewinnt, hängt von Ihrer genauen Situation ab.

Im Gegensatz zur Version itertools werden doppelte Paare nur dann zurückgegeben, wenn beide Elemente doppelt vorhanden sind. ZB, betrachte eine Liste von [4, 3, 6, 6]. Die itertools Version erzeugt zwei verschiedene (4, 6) Paare und gibt sie beide zurück; Diese Version berücksichtigt die 4 konsumiert, sobald es auf die ersten 6 abgestimmt ist und wird nur eins zurückgeben. Wenn eine Duplizierung erwünscht ist, würde ein set anstelle eines Counter funktionieren - obwohl der spezielle Fall für 5 komplizierter wird, es sei denn, Sie erstellen den Satz iterativ, wie in @ lollercoasters Antwort gezeigt.

Answer 5

Alle waren bisher O (N^2) oder noch schlimmer, also hier ist eine O (N) Lösung:

l = [7, 9, 6, 4, 2] 
s = set([l[0]]) 
sum = 10 
for num in l[1:]: 
    diff = sum - num 
    if diff in s: 
     print num, diff 
    else: 
     s.add(num) 

Da der OP gefragt, hier ist ein allgemeiner Blick auf die Lösung.Wir haben:

• numbers (Liste von Zahlen)
• sum (gewünschte Summe)
• n (Anzahl der Elemente, die wir zu sum fassen wollen)

Am einfachsten ist die folgende:

def find_sum_tuple(numbers, sum, n): 
    return [tup for tup in itertools.combinations(numbers, n) if sum(tup) == sum] 

Allerdings nicht das beste in Begriff s asymptotischer Leistung. Wie ich oben gezeigt habe, sollten Sie in der Lage sein, asymptotische O (| numbers |^(n -1)) zu erhalten, indem Sie cleverere und zwischengespeicherte Summen von n - 1 Größe verwenden.

Answer 6

lst = [5,2,3,9,1] 

lstLen = len(lst) 

pair = 0 

for i in range(lstLen): 

    for j in range(lstLen): 
     if(j <= i): continue 
     if((lst[i] + lst[j]) == 10): 
      pair +=1 
      print "[%s, %s]" % (lst[i], lst[j]) 

print "number of pair = %s" % pair 

Answer 7

#for unsorted array - complexity O(n) 

def twoSum(arr, target): 
    hash = {} 

    if len(arr) < 2: 
    return None 

    for i in range(len(arr)): 
    if arr[i] in hash: 
     return [hash[arr[i]], i] 
    else: 
     hash[target - arr[i]] = i 
    return None 

twoSum([3,2,8,6],11)