Clever Geek Handbook

How to iterate over and sum each item in a list with another to find a number?

I was doing some programming and this question came across, I got stuck with it somehow. I was given a list: [10, 13, 15, 18, 20, 15]

And I had to find if the sum of any element in this would provide a result of 30 and the output should be a counter As we could see we have two possibilities: 10 + 20 = 30 and 15 + 15, so a counter is 2. But how to do it, should it be used for loop or itertools or any cut or functional solution?

+3


source to share


4 answers


You can use a itetools.combinations

generator expression in sum

:

>>> my_list=[10, 13, 15, 18, 20, 15]
>>> from itertools import combinations
>>> sum(i+j==30 for i,j in combinations(my_list,2))
2


And if you also want these elements to be able to use a list comprehension:

>>> [(i,j) for i,j in combinations(my_list,2) if i+j==30]
[(10, 20), (15, 15)]
+5


source 


>>> from itertools import combinations
>>> lst = [10, 13, 15, 18, 20, 15]
>>> count = 0
>>> for x, y in combinations(lst, 2):
        if x + y == 30:
            print(x, y)
            count += 1

10 20
15 15

>>> print(count)
2


+4


source


Or if you don't want to use itertools you can do it with the following list comprehension

 len([(ii,jj) for i, ii in enumerate(a) for j, jj in enumerate(a[i+1:]) if ii+jj==30])

which gives you

 len([(10, 20), (15, 15)]) = 2

Combinations are approached in about half the time.

+3


source


Since this is due to a programming problem, here is a solution that has linear complexity in the length of the list (using combinations, you get quadratic complexity):

from collections import defaultdict
def count_pairs_summing_to(lst, n):  
    element_counter = defaultdict(int)
    count = 0
    for x in lst:
        if (n - x) in element_counter:
            count += element_counter[n - x]
        element_counter[x] += 1
    return count

The idea is to do one pass over the data and keep track of the elements we saw earlier in the hash table. When we see a new element x

, we only need to know if we have seen it before 30 - x

.
We also keep track of how many times we've seen each item to make sure we're counting duplicate pairs (for example, count_pairs_summing_to([10, 10, 20, 25], 30)

should return 2.).

Some benchmarking:

lst = [10, 13, 15, 18, 20, 15]

%timeit sum(i+j==30 for i,j in combinations(lst,2))
100000 loops, best of 3: 3.35 µs per loop

%timeit len([(ii,jj) for i, ii in enumerate(lst) for j, jj in enumerate(lst[i+1:]) if ii+jj==30])
100000 loops, best of 3: 6.59 µs per loop

%timeit count_pairs_summing_to(lst, 30)
100000 loops, best of 3: 2.92 µs per loop

# With a slightly bigger list.
import numpy.random as random
big_lst = list(random.randint(0, 100, size=1000))

%timeit len([(ii,jj) for i, ii in enumerate(big_lst) for j, jj in enumerate(big_lst[i+1:]) if ii+jj==30])
10 loops, best of 3: 125 ms per loop

%timeit sum(i+j==30 for i,j in combinations(big_lst,2))
1 loops, best of 3: 1.21 s per loop

# The previous one was surprisingly slow but it can be fixed:
%timeit sum(1 for i,j in combinations(big_lst,2) if i+j==30)
1 loops, best of 3: 88.2 ms per loop

%timeit count_pairs_summing_to(big_lst, 30)
1000 loops, best of 3: 504 µs per loop
0


source






More articles:


All Articles