Как найти парные суммы в списке?

Question

У меня есть список x

[1, 2, 3, 3, 5, 5, 6, 7, 8, 9, 9]

, и я хочу найти всю сумму пары, равную 10,

, и это должны быть разные пары чисел:

то есть

{(1, 9), (2, 8), (3, 7), (5, 5)}.

вот мысли, но я не доволен вложенным циклом ниже:

def test(x, n):
   pair = set()
   for i in range(len(x)):
        for j in range(len(x)):
            if i !=j:
               pair.add((x[i],x[j])

Answer 1

@ Решение ThierryLathuille предполагает, что список предварительно отсортирован. Если это предположение неверно, сортировка списка будет стоить O (n log n) . Вместо этого вы можете использовать collections.Counter для достижения O (n) сложности времени при учете количества доступных элементов для каждого значения в списке:

from collections import Counter
counts = Counter(x)
list({frozenset((10 - n, n)): (10 - n, n) for n in counts if counts[10 - n] > (n == 10 - n)}.values())

Возвращает:

[(1, 9), (2, 8), (3, 7), (5, 5)]

Answer 2

Понимание списка здесь будет хорошо работать.Попробуйте это:

from itertools import permutations

x = [1, 2, 3, 3, 5, 5, 5, 6, 6, 7, 8, 9, 9]
target_number = 10

solutions = [pair for pair in permutations(x, 2) if sum(pair) == 10]
print('Solutions:', solutions)

Вывод:

Solutions: [(1, 9), (1, 9), (2, 8), (3, 7), (3, 7), (5, 5), (5, 5), (5, 5), (5, 5), (5, 5), (5, 5), (7, 3), (7, 3), (8, 2), (9, 1), (9, 1)]

По сути, это понимание списка рассматривает все пары, которые возвращает permutations(x, 2), но сохраняет только течья общая сумма равна 10.

Answer 3

Как на счет этого

x=[1, 2, 3, 3, 5, 5, 6, 7, 8, 9, 9]
y=[]
for i in x[:5]:
    q=10-i 
    w=(i,q)
    if ((q in x) & (not(w in y))):
        y.append(w)

это может быть неэффективный код для замены вашего, моя точка зрения на этот код - просто альтернатива вашему вложенному циклу

Answer 4

Решение в O (n), работающее с отсортированным списком значений:

values = [1, 2, 3, 3, 5, 5, 6, 7, 8, 9, 9]
target = 10

i = 0
j = len(values) - 1
solutions = set()

while j > i:
    if values[i] + values[j] < target:
        i += 1
    elif values[i] + values[j] > target:
        j -= 1
    else:
        solutions.add((values[i], values[j]))
        i += 1
        j -= 1

print(solutions)
# {(2, 8), (5, 5), (1, 9), (3, 7)}

Answer 5

Если мы знаем общее количество, которое мы хотим, мы можем задать вопрос - для каждого числа есть (общее число) в списке?

Мы можем превратить список в набор для использования хешированного поиска:

x = [1, 2, 3, 3, 5, 5, 5, 6, 6, 7, 8, 9, 9]

out = []
total = 10
for i in set(x):
    if (total - i) in set(x) and i < (total+1)/2:
        out.append((i, 10-i))
out

[(1, 9), (2, 8), (3, 7), (5, 5)]

Answer 6

Однострочник, не самый эффективный:

import itertools

res = set([pair for pair in itertools.combinations(x, 2) if sum(pair)==10])

# {(2, 8), (5, 5), (9, 1), (3, 7)}

Вы платите дополнительно за создание здесь дополнительных комбинаций, а также накладные расходы конструктора set (не уверен, что вы сможете обойти последний)

Answer 7

Вы также можете получить решение O (n), используя набор для хранения различных значений.Вы должны принять во внимание цели, которые являются четными числами.Даже для целей потребуются два экземпляра их половинного значения в списке, но набор не будет проводить это различие и может найти пару равных значений, когда в списке фактически есть только одно (например, target = 12 в ваших примерах значений).

values = [1, 2, 3, 3, 5, 5, 6, 7, 8, 9, 9]
target = 10

valueSet  = set(values)
halfValue = target//2
if 2*halfValue == target and values.count(halfValue) < 2: halfValue -= 1
result   = [ (v,target-v) for v in valueSet if v <= halfValue and target-v in valueSet ]