3

Given a list of integers, I want to check a second list and remove from the first only those which can not be made from the sum of two numbers from the second. So given a = [3,19,20] and b = [1,2,17], I'd want [3,19].

Seems like a a cinch with two nested loops - except that I've gotten stuck with break and continue commands.

Here's what I have:

def myFunction(list_a, list_b):
    for i in list_a:
        for a in list_b:
            for b in list_b:
                    if a + b == i:
                        break
                    else:
                        continue
                    break
                else:
                    continue
            list_a.remove(i)
    return list_a

I know what I need to do, just the syntax seems unnecessarily confusing. Can someone show me an easier way? TIA!

6
  • What if a contains a = [3, 4, 19, 20]? Then there are two possible sums: 3+20 and 4+19, so what to remove in that case? Jan 21, 2018 at 13:32
  • Sort b and use binary search...?
    – cs95
    Jan 21, 2018 at 13:34
  • 19 can also be made with 2+17. Also how can 3 be made from sum of 2 elements of list B?
    – rnso
    Jan 21, 2018 at 13:35
  • Sorry, I carelessly used an incorrect example - fixed it now. Jan 21, 2018 at 13:39
  • @JohnColeman: yes, just because I'm approaching it by removing those which cannot be made. Earlier I was trying to list all of those from a which can be made, and then remove the duplicates, but that seemed less efficient. Jan 21, 2018 at 13:47

4 Answers 4

4

You can do like this,

In [13]: from itertools import combinations
In [15]: [item for item in a if item in [sum(i) for i in combinations(b,2)]]
Out[15]: [3, 19]

combinations will give all possible combinations in b and get the list of sum. And just check the value is present in a

Edit

If you don't want to use the itertools wrote a function for it. Like this,

def comb(s):
    for i, v1 in enumerate(s):
        for j in range(i+1, len(s)):
            yield [v1, s[j]]

result = [item for item in a if item in [sum(i) for i in comb(b)]]
2
  • Thanks! This is great, but I'm trying to solve it without import statements - it's part of a (longer, more complicated) homework task. Jan 21, 2018 at 13:43
  • 1
    @JoshFriedlander Updated the answer.
    – Rahul K P
    Jan 21, 2018 at 13:51
1

Comments on code:

  • It's very dangerous to delete elements from a list while iterating over it. Perhaps you could append items you want to keep to a new list, and return that.
  • Your current algorithm is O(nm^2), where n is the size of list_a, and m is the size of list_b. This is pretty inefficient, but a good start to the problem.
  • Thee's also a lot of unnecessary continue and break statements, which can lead to complicated code that is hard to debug.
  • You also put everything into one function. If you split up each task into different functions, such as dedicating one function to finding pairs, and one for checking each item in list_a against list_b. This is a way of splitting problems into smaller problems, and using them to solve the bigger problem.

Overall I think your function is doing too much, and the logic could be condensed into much simpler code by breaking down the problem.

Another approach:

Since I found this task interesting, I decided to try it myself. My outlined approach is illustrated below.

1. You can first check if a list has a pair of a given sum in O(n) time using hashing:

def check_pairs(lst, sums):
    lookup = set()

    for x in lst:
        current = sums - x
        if current in lookup:
            return True
        lookup.add(x)

    return False

2. Then you could use this function to check if any any pair in list_b is equal to the sum of numbers iterated in list_a:

def remove_first_sum(list_a, list_b):
    new_list_a = []

    for x in list_a:
        check = check_pairs(list_b, x)
        if check:
            new_list_a.append(x)

    return new_list_a

Which keeps numbers in list_a that contribute to a sum of two numbers in list_b.

3. The above can also be written with a list comprehension:

def remove_first_sum(list_a, list_b):
    return [x for x in list_a if check_pairs(list_b, x)]

Both of which works as follows:

>>> remove_first_sum([3,19,20], [1,2,17])
[3, 19]
>>> remove_first_sum([3,19,20,18], [1,2,17])
[3, 19, 18]
>>> remove_first_sum([1,2,5,6],[2,3,4])
[5, 6]

Note: Overall the algorithm above is O(n) time complexity, which doesn't require anything too complicated. However, this also leads to O(n) extra auxiliary space, because a set is kept to record what items have been seen.

2
  • Please let me know if I have overlooked something here.
    – RoadRunner
    Jan 21, 2018 at 14:34
  • Very helpful, thank you! Time complexity was very relevant here, so I ended up using a modified version of your answer. Jan 22, 2018 at 10:26
1

You can do it by first creating all possible sum combinations, then filtering out elements which don't belong to that combination list

Define the input lists

>>> a = [3,19,20]
>>> b = [1,2,17]

Next we will define all possible combinations of sum of two elements

>>> y = [i+j for k,j in enumerate(b) for i in b[k+1:]]

Next we will apply a function to every element of list a and check if it is present in above calculated list. map function can be use with an if/else clause. map will yield None in case of else clause is successful. To cater for this we can filter the list to remove None values

>>> list(filter(None, map(lambda x: x if x in y else None,a)))

The above operation will output:

>>> [3,19]

You can also write a one-line by combining all these lines into one, but I don't recommend this.

0

you can try something like that:

a = [3,19,20]
b=  [1,2,17,5]

n_m_s=[]
data=[n_m_s.append(i+j) for i in b for j in b  if i+j in a]

print(set(n_m_s))

print("after remove")

final_data=[]
for j,i in enumerate(a):
    if i not in n_m_s:
        final_data.append(i)

print(final_data)

output:

{19, 3}
after remove
[20]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.