Я пытаюсь найти комбинацию для суммы внутри списка целых чисел.нахождение суммы чисел X в списке (Python)
количество чисел, которые содержат сумму ограничена переменной, так например, в списке -
[5,2,3,9,1], я хотел бы найти сумму 10 , всего 2 числа.
, чтобы программа распечатывала [9,1].
Я новичок в python, есть ли простой способ сделать это?
спасибо.
грубой силы подход, использующий itertools.combinations:
In [6]: [pair for pair in itertools.combinations(li,2) if sum(pair) == 10]
Out[6]: [(9, 1)]
Это дает вам все пары эту сумму до 10. Это сверхэкспоненциального во время выполнения, так что если ваши входы велики вы хотите более сложный алгоритм.
Я думаю, что вы могли бы теоретически сэкономить время обработки, используя тот факт, что, узнав свой первый номер, вы также знаете второй и можете проверить его присутствие в списке (возможно, используя объект 'collections.Counter', созданный из списка чтобы ускорить повторные тесты членства, уменьшая при выводе каждой пары), но это становится более запутанным, чем это. Ясность, вероятно, побеждает в подавляющем большинстве случаев. –
@PeterDeGlopper да, я добавил примечание о временной сложности. Я полагаю, что для большинства применений этого достаточно. – roippi
Почему downvote? Это вполне законный ответ. –
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 создать все возможные комбинации tuples из итерации объекта (объекта Вы можете перебираешь). Позвольте мне продемонстрировать:
>>> [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)]
Почему голос? –
ls = [5, 2, 3, 9, 1]
sum = 10
while ls:
num = ls.pop()
diff = sum - num
if diff in ls:
print([num, diff])
Только для целей код гольфа, вот 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 был добавлен в 2.7. Для более ранних версий вам нужно будет использовать defaultdict. Это не намного сложнее.
Я думаю, что это труднее читать, чем версия itertools.combinations @roippi, но она должна быть значительно быстрее, если список целых чисел велик. Обычно я ценю человеческое время, считывая код за время, затрачиваемое машиной, но выигрыш от этого будет зависеть от вашей конкретной ситуации.
В отличие от версии itertools, это не будет возвращать повторяющиеся пары, если оба элемента не дублируются. EG, рассмотрим список [4, 3, 6, 6]. Версия itertools будет генерировать две разные пары (4, 6) и вернуть их оба; эта версия рассматривает 4 потребляемых, как только он соответствует первым 6 и будет возвращать только один. Если требуется дублирование, будет работать set вместо Counter, хотя специальный случай для 5 становится более сложным, если вы не создадите набор итеративно, как показано в ответе @ lollercoaster.
Все до сих пор были O (N^2) или хуже, так вот O (N) решение:
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)
Поскольку ОП спросил, вот более общий взгляд на решение.Мы имеем:
numbers (список номеров)sum (желаемая сумма)n (количество элементов, которые мы желаем, чтобы подвести к sum)Самый простой заключается в следующем:
def find_sum_tuple(numbers, sum, n):
return [tup for tup in itertools.combinations(numbers, n) if sum(tup) == sum]
Однако, не самый лучший в срочном порядке s асимптотических характеристик. Как я показал выше, вы должны получить асимптотику O (| numbers |^(n -1)), будучи более умными и кэширующими суммами n - 1.
Я не согласен с тем, что мое решение «Counter» равно O (N^2). Один обход для создания «Counter», один обход для поиска пар и поиск в N словарях. Эта версия близка к моей, но не может корректно обрабатывать такие случаи, как '[4, 6, 6]'. Я думаю, что есть какая-то польза в этой идее - просто используйте 'Counter' вместо' set', и вы можете получить преимущества производительности от повторения только один раз. В зависимости от того, насколько быстрее конструктор 'Counter' может обрабатывать список, а не делать несколько изменений, реализация C может превзойти алгоритмическое улучшение. –
Правда, но с учетом вопроса задает «комбинацию», а не «все комбинации», это отвечает на вопрос в 2N, а не на 3N. На самом деле это не так, потому что да, мы оба линейны! – lollercoaster
Да, O (N), а не O (N^2) - это все, что обычно важно. И оказывается, что может быть важно, что такое поведение на возможных дубликатах - 'itertools' найдет (4,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
#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)
Итак, вы хотите, чтобы найти то, что два числа в списке при сложении равен 10? – jramirez
Посмотрите на модуль itertools. – rlms