How to check for common elements between two lists in python

Question

I am having a bit of trouble when I try and check for overlapping elements in list.

This means that I will have to check for common elements between two lists.

The way in which my programme works is that the player enters their two end coordinates for a certain ship, it then creates a list out of this of all of the ships coordinates (ie if they enter (1,1) and (1,5), it would create [(1,1),(1,2),(1,3),(1,4),(1,5)]

I have also tried using the following code but it doesn't work for the way I want it to:

ListA = [(1,1),(1,2),(1,3),(1,4),(1,5)]
ListB = [(1,1),(2,1),(3,1)]

    for i in ListB:
        if i in ListA:
            print("There is an overlap")
            #choose coordinates again
        else:
            print("There is no overlap")
            #add to ListA and next ship's coordinate chosen

I would like for the program to check to see if any of the elements in A are in B by considering them collectively, instead of checking them individually.

Answer 1

set.intersection will find any common elements:

ListA = [(1,1),(1,2),(1,3),(1,4),(1,5)]
ListB = [(1,1),(2,1),(3,1)]
print(set(ListA).intersection(ListB))
set([(1, 1)])

Unless order matters it may be just as well to store the tuples in sets:

st_a = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5)}
st_b = {(1, 1), (2, 1), (3, 1)}
print(st.intersection(st_b))

add it to your code with:

if st_a.intersection(st_b):
     print("There is an overlap")            
else:
    print("There is no overlap")

Answer 2

If there is an overlap you want to choose coordinates again;

for i in ListB:
    if i in ListA:
        print("There is an overlap")
        i=(yourcoordinateshere)

Else you want to add it to ListA;

else:
    print("There is no overlap")
    ListA.append(i)

Answer 3

Not sure if this helps...

In [1]: from collections import Counter

In [2]: import random

In [3]: lst = [random.randrange(0, 9) for i in xrange(1000)]

In [4]: counted = Counter(lst)

In [7]: counted.most_common(10)
Out[7]: 
[(2, 125),
 (0, 123),
 (5, 120),
 (8, 118),
 (7, 111),
 (1, 107),
 (4, 104),
 (6, 102),
 (3, 90)]

Answer 4

Dictionary

If in practice:

 len(ListA) * len(ListB) * ExpectedNumberOfCollisionChecks

is significant then it may make sense to use a dictionary for the longer list because the time complexity for a dictionary lookup is:

• Average: O(1)
• Worst case: O(n)

Where the average is expected and the worst case happens only when a bad hash function has been selected.

Intersecting Sets

The accepted answer proposes using set.intersection. The time complexity of set.intersection is:

• Average: O(n)
• Worst case: O(n^2)

Modified Code

The only change to your original code is conversion of ListA to MapA.

MapA = {(1,1): True, (1,2): True, (1,3): True,(1,4): True, (1,5): True}
ListB = [(1,1),(2,1),(3,1)]

for i in ListB:
    if MapA.get(i):
        print("There is an overlap")
        #choose coordinates again
    else:
        print("There is no overlap")
        #add to ListA and next ship's coordinate chosen

Comments

Going further, the entire intersection operation has to be run each time the user inputs new coordinates (i.e. ListB changes). On the other hand the expensive operation most expensive operation: hashing ListA, only occurs once. Insertions and deletions from a dictionary have good time complexity:

• Average: O(1)
• Worst case: O(n)

For lists, if order does not matter then inserting into a list is always O(1) and regardless of if we care about order deletions are always O(n).