Próbuję znaleźć kombinację dla sumy na liście liczb całkowitych.znajdowanie sumy liczb X w liście (Python)
ilość numerów, które zawierają kwotę ograniczona jest zmienna, tak, na przykład, w liście -
[5,2,3,9,1], czy i jak znaleźć sumę 10 , tylko z 2 cyframi.
, aby program wydrukował [9,1].
Jestem nowy dla Pythona, czy istnieje prosty sposób na zrobienie tego?
dziękuję.
Podejście brute-force użyciu itertools.combinations:
In [6]: [pair for pair in itertools.combinations(li,2) if sum(pair) == 10]
Out[6]: [(9, 1)]
Daje to wszystkie pary tej kwoty do 10. Jest to superexponential w czasie wykonywania, więc jeśli są duże nakłady będą chcesz bardziej skomplikowany algorytm.
Myślę, że teoretycznie mógłbyś zaoszczędzić trochę czasu przetwarzania, wykorzystując fakt, że gdy znasz swój pierwszy numer, znasz także drugi i możesz sprawdzić jego obecność na liście (prawdopodobnie za pomocą obiektu 'collections.Counter' utworzonego z listy przyśpieszać powtarzane testy członkostwa, zmniejszając się w miarę wyprowadzania każdej pary), ale staje się to bardziej mylące. Klarowność prawdopodobnie wygrywa w zdecydowanej większości przypadków. –
@PeterDeGlopper tak, dodałem notatkę o złożoności czasu. Wyobrażam sobie, że dla większości zastosowań jest to wystarczające. – roippi
Dlaczego downvote? To jest całkowicie uzasadniona odpowiedź. –
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 utworzyć wszystkie możliwe kombinacje tuples z iterowalny przedmiotu (obiektu możesz pętli nad). Pozwól mi zademonstrować:
>>> [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)]
Dlaczego głosowanie w dół? –
ls = [5, 2, 3, 9, 1]
sum = 10
while ls:
num = ls.pop()
diff = sum - num
if diff in ls:
print([num, diff])
Tylko dla celów Kod golfowych, tutaj jest podejście collections.Counter:
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 dodano 2,7. W przypadku wcześniejszych wersji należy użyć wartości defaultdict. To nie jest bardziej skomplikowane.
Myślę, że jest to trudniejsze do odczytania niż opublikowana wersja @roippi z itertools.combinations, ale powinna być znacznie szybsza, jeśli lista liczb całkowitych jest duża. Zwykle oceniam ludzki czas czytania kodu przez czas maszynowy, który go wykonuje, ale to, co wygrywa, zależy od twojej konkretnej sytuacji.
W przeciwieństwie do wersji itertools nie zwróci ona duplikatów, chyba że oba elementy zostaną zduplikowane. EG, rozważ listę [4, 3, 6, 6]. Wersja itertools wygeneruje dwie różne pary (4, 6) i zwróci je obie; ta wersja uwzględnia 4 zużyte, gdy tylko zostaną dopasowane do pierwszych 6 i zwróci tylko jeden. Jeśli pożądane jest powielanie, zadziała set zamiast Counter - chociaż specjalny przypadek dla 5 będzie bardziej skomplikowany, chyba że zbudujesz zestaw iteracyjnie jak w odpowiedzi @ lollercoaster.
Wszystko do tej pory było O (n^2) lub, co gorsza, więc tutaj jest O (N) rozwiązanie:
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)
Ponieważ PO poprosił, tutaj jest bardziej ogólny wygląd w roztworze.Mamy:
numbers (lista numerów)sum (wymagana suma)n (liczba elementów pragniemy podsumować do sum)Najprostszym jest następujący:
def find_sum_tuple(numbers, sum, n):
return [tup for tup in itertools.combinations(numbers, n) if sum(tup) == sum]
Jednak nie najlepszy termin s wydajności asymptotycznej. Jak pokazałem powyżej, powinieneś być w stanie uzyskać asymptotyczny O (| numbers |^(n -1)), będąc bardziej sprytnym i buforującym sumami o rozmiarze n - 1.
Nie zgadzam się, że moje rozwiązanie 'Counter' to O (N^2). Jedno przejście do utworzenia 'Counter', jednego przejścia do wyszukiwania par i wyszukiwania słownika N. Ta wersja jest bliska mojej, ale nie obsługuje poprawnie takich przypadków jak '[4, 6, 6]'. Sądzę jednak, że pomysł ma pewne zalety - po prostu użyj 'Counter' zamiast' set', a możesz uzyskać korzyści wydajnościowe z iterowania tylko raz. W zależności od tego, o ile szybciej konstruktor 'Counter' może obsłużyć listę, zamiast dokonywać wielu zmian - implementacja C może pokonać ulepszenie algorytmiczne. –
To prawda, ale biorąc pod uwagę pytanie o "kombinację", a nie "wszystkie kombinacje", odpowiada to na pytanie w 2N, a nie na 3N. Co naprawdę nie jest tak różne - więc tak, oboje jesteśmy liniowi! – lollercoaster
Tak, O (N) zamiast O (N^2) to wszystko, co zwykle ważne. I okazuje się, że ważne może być zachowanie na możliwych duplikatach - "itertools" znalazłby (4,6) dwa razy w tym mini-przykładzie. OP nie określił, więc twoja wersja może być bliżej celu. –
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
#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)
Więc chcesz znaleźć co dwa numery na liście razem wziętych równa 10? – jramirez
Zobacz moduł itertools. – rlms