Better ways to find pairs that sum to N

Question

Is there a faster way to write this, the function takes a list and a value to find the pairs of numeric values in that list that sum to N without duplicates I tried to make it faster by using sets instead of using the list itself (however I used count() which I know is is linear time) any suggestions I know there is probably a way

def pairsum_n(list1, value):

    set1 = set(list1)
    solution = {(min(i, value - i) , max(i, value - i)) for i in set1 if value - i in set1}
    solution.remove((value/2,value/2)) if list1.count(value/2) < 2 else None           
    return solution
"""
    Example: value = 10, list1 = [1,2,3,4,5,6,7,8,9]
    pairsum_n = { (1,9), (2,8), (3,7), (4,6) }
    Example: value = 10,  list2 = [5,6,7,5,7,5,3]
    pairsum_n = { (5,5), (3,7) }
"""

Answer 1

Have another solution, it's alot faster then the one I just wrote, not as fast as @PM 2Ring's answer:

def pairsum_n(list1, value):
    set1 = set(list1)
    if list1.count(value/2) < 2:
        set1.remove(value/2)
    return set((min(x, value - x) , max(x, value - x)) for x in filterfalse(lambda x: (value - x) not in set1, set1))

Answer 2

Try this, running time O(nlogn):

v = [1, 2, 3, 4, 5, 6, 7, 8, 9]
l = 0
r = len(v)-1

def myFunc(v, value):

    ans = []

    % this block search for the pair (value//2, value//2)
    if value % 2 == 0:
        c = [i for i in v if i == value // 2]
        if len(c) >= 2:
            ans.append((c[0], c[1]))

    v = list(set(v))
    l = 0
    r = len(v)-1
    v.sort()
    while l<len(v) and r >= 0 and l < r:
        if v[l] + v[r] == value:
            ans.append((v[l], v[r]))
            l += 1
            r -= 1
        elif v[l] + v[r] < value:
            l += 1
        else:
            r -= 1

    return list(set(ans))

It is called the Two pointers technique and it works as follows. First of all, sort the array. This imposes a minimum running time of O(nlogn). Then set two pointers, one pointing at the start of the array l and other pointing at its last element r (pointers name are for left and right).

Now, look at the list. If the sum of the values returned at position l and r is lower than the value we are looking for, then we need to increment l. If it's greater, we need to decrement r.

If v[l] + v[r] == value than we can increment/decrement both l or r since in any case we want to skip the combination of values (v[l], v[r]) as we don't want duplicates.

Answer 3

Your approach is quite good, it just needs a few tweaks to make it more efficient. itertools is convenient, but it's not really suitable for this task because it produces so many unwanted pairs. It's ok if the input list is small, but it's too slow if the input list is large.

We can avoid producing duplicates by looping over the numbers in order, stopping when i >= value/2, after using a set to get rid of dupes.

def pairsum_n(list1, value): 
    set1 = set(list1)
    list1 = sorted(set1)
    solution = []
    maxi = value / 2
    for i in list1:
        if i >= maxi:
            break
        j = value - i
        if j in set1:
            solution.append((i, j))
    return solution

Note that the original list1 is not modified. The assignment in this function creates a new local list1. If you do actually want (value/2, value/2) in the output, just change the break condition.

---

Here's a slightly more compact version.

def pairsum_n(list1, value): 
    set1 = set(list1)
    solution = []
    for i in sorted(set1):
        j = value - i
        if i >= j:
            break
        if j in set1:
            solution.append((i, j))
    return solution

It's possible to condense this further, eg using itertools.takewhile, but it will be harder to read and there won't be any improvement in efficiency.

Answer 4

Timings: this is actually slower then the other 2 solutions. Due to the amount of combinations produced but not actually needed it gets worse the bigger the lists are.

---

You can use itertools.combinations to produce the 2-tuple-combinations for you.

Put them into a set if they match your value, then return as set/list:

from itertools import combinations 

def pairsum_n(list1, value): 
    """Returns the unique list of pairs of combinations of numbers from 
    list1 that sum up `value`. Reorders the values to (min_value,max_value)."""
    result = set()
    for n in combinations(list1, 2):
        if sum(n) == value:
            result.add( (min(n),max(n)) )
    return list(result)

    # more ugly one-liner:
    # return list(set(((min(n),max(n)) for n in combinations(list1,2) if sum(n)==value)))

data = [1,2,3,4,5,6,6,5,4,3,2,1]

print(pairsum_n(data,7))

Output:

[(1, 6), (2, 5), (3, 4)]

---

Fun little thing, with some sorting overhead you can get all at once:

def pairsum_n2(data, count_nums=2):
    """Generate a dict with all count_nums-tuples from data. Key into the
    dict is the sum of all tuple-values."""
    d = {}
    for n in (tuple(sorted(p)) for p in combinations(data,count_nums)):
        d.setdefault(sum(n),set()).add(n)
    return d

get_all =  pairsum_n2(data,2) # 2 == number of numbers to combine
for k in get_all:
    print(k," -> ", get_all[k])

Output:

 3  ->  {(1, 2)}
 4  ->  {(1, 3), (2, 2)}
 5  ->  {(2, 3), (1, 4)}
 6  ->  {(1, 5), (2, 4), (3, 3)}
 7  ->  {(3, 4), (2, 5), (1, 6)}
 2  ->  {(1, 1)}
 8  ->  {(2, 6), (4, 4), (3, 5)}
 9  ->  {(4, 5), (3, 6)}
10  ->  {(5, 5), (4, 6)}
11  ->  {(5, 6)}
12  ->  {(6, 6)}

And then just access the one you need via:

print(get_all.get(7,"Not possible"))    #  {(3, 4), (2, 5), (1, 6)}
print(get_all.get(17,"Not possible"))   #  Not possible