[Tutor] Trying to find all pairs of numbers from list whose sum is 10

[Peter Otten]

On 19/06/2021 22:24, Oscar Benjamin wrote:
> On Sat, 19 Jun 2021 at 19:25, Manprit Singh <manpritsinghece at gmail.com> wrote:
>>
>> Dear sir,
>>
>> Let us consider a list
>> lst = [2, 4, 7, 5, 9, 0, 8, 5, 3, 8]
>> in this list there are 3 pairs (2, 8), (5, 5), (7, 3) whose sum is 10. To
>> finding these pairs i have written the code as below :
>>
>> def pair_ten(x):
>>      y, st  = x[:], set()
>>      for i in x:
>>          y.remove(i)
>>          st.update((i, ele) for ele in y if i+ele == 10)
>>      return st
>>
>> lst = [2, 4, 7, 5, 9, 0, 8, 5, 3, 8]
>> ans = pair_ten(lst)
>> print(ans)
>>
>> {(2, 8), (5, 5), (7, 3)}
>>
>> But i feel the code is still more complex, due to two for loops, in
>> what way this ccan be dome more efficiently.
> 
> What does "more efficiently" mean? What is the scope of this problem?
> Are the numbers always positive? Do you only want this for summing to
> 10 or is that just an example?
> 
> The task as stated finding pairs that sum to 10 can be done very
> easily if all inputs are assumed to be positive:
> 
> def pair_ten(numbers):
>      numbers_set = set(numbers)
>      pairs10 = []
>      for i in range(5+1):
>          if i in numbers_set:
>              i10 = 10 - i
>              if i10 in numbers_set:
>                  pairs10.append((i, i10))
>      return pairs10

lst=[6, 4, 6]
manprit: {(6, 4), (4, 6)}
alan: [(6, 4), (4, 6)]
oscar: [(4, 6)]

lst=[5]
manprit: set()
alan: []
oscar: [(5, 5)]

Efficiency considerations aside:

Are the tuples meant to be ordered?
Can one number in the original list be reused for both entries of a tuple?

> 
> This only has one for loop. Your version has two as well as a hidden
> loop in the call to y.remove.
> 
> Alan's version is nice and simple and works fine for small inputs but
> would be horribly inefficient if the size of the input list was large.
> You haven't said whether it could be large though (if it's always
> small then you are probably overthinking this). The version I showed
> above would be inefficient if numbers was a small list and you were
> looking for pairs that sum to say 1 million rather than 10. Also the
> implementation I showed above converts the numbers list to a set which
> is O(N) with no possibility of an early exit. If numbers was a huge
> list that contained all the possible pairs many times then it could be
> much quicker to loop through the first hundred or so items to see that
> all 5 possible pairs are there rather than convert the entire list to
> a set before doing anything else.
> 
> More information is needed to say what is actually efficient.