CODEWITHSUNDEEP
pythonlist
Dave
Dave

Reputation: 1001

Finding elements not in a list

So heres my code:

item = [0,1,2,3,4,5,6,7,8,9]
z = []  # list of integers

for item in z:
    if item not in z:
        print item

z contains a list of integers. I want to compare item to z and print out the numbers that are not in z when compared to item.

I can print the elements that are in z when compared not item, but when I try and do the opposite using the code above nothing prints.

Any help?

Upvotes: 99

Views: 285382

Answers (12)

BrokenBenchmark
BrokenBenchmark

Reputation: 19242

Many of the solutions already posted here will not preserve the original ordering of the elements (because sets are unordered) or are inefficient (because linear search in a list is slower than a lookup in a set).

You can make a set of elements to remove upfront, and then use a list comprehension to retain only the elements which aren't in the set:

items = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
z = [3, 4, 5, 6]

set_z = set(z)
result = [e for e in items if e not in set_z]

Then, result contains:

[0, 1, 2, 7, 8, 9]

Upvotes: 2

vinayman
vinayman

Reputation: 572

If the lists are sorted and you know the elements of the checking list are in the base list - you can do a more optimal O(n) solution by using two pointers (where n will be the length of the base_list:

base_list = [0, 1, 2, 3, 4, 5, 6, 7, 8]
checking_list = [1, 3, 5]

expected_return = [0, 2, 4, 6, 7, 8]

j = 0
i = 0
elements_not_in_checking_list = []
while i < len(base_list):
    if j < len(checking_list) and base_list[i] == checking_list[j]:
        i += 1
        j += 1
    else:
        elements_not_in_checking_list.append(base_list[i])
        i += 1

Upvotes: 0

ezod
ezod

Reputation: 7421

Your code is not doing what I think you think it is doing. The line for item in z: will iterate through z, each time making item equal to one single element of z. The original item list is therefore overwritten before you've done anything with it.

I think you want something like this:

item = [0,1,2,3,4,5,6,7,8,9]

for element in item:
    if element not in z:
        print(element)

But you could easily do this like:

[x for x in item if x not in z]

or (if you don't mind losing duplicates of non-unique elements):

set(item) - set(z)

Upvotes: 221

Warin Isvilanonda
Warin Isvilanonda

Reputation: 11

In the case where item and z are sorted iterators, we can reduce the complexity from O(n^2) to O(n+m) by doing this

def iexclude(sorted_iterator, exclude_sorted_iterator):
    next_val = next(exclude_sorted_iterator)
    for item in sorted_iterator:
        try:
            while next_val < item:
                next_val = next(exclude_sorted_iterator)
                continue
            if item == next_val:
                continue
        except StopIteration:
            pass
        yield item

If the two are iterators, we also have the opportunity to reduce the memory footprint not storing z (exclude_sorted_iterator) as a list.

Upvotes: 1

VDV
VDV

Reputation: 904

Using list comprehension:

print [x for x in item if x not in Z]

or using filter function :

filter(lambda x: x not in Z, item)

Using set in any form may create a bug if the list being checked contains non-unique elements, e.g.:

print item

Out[39]: [0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9]

print Z

Out[40]: [3, 4, 5, 6]

set(item) - set(Z)

Out[41]: {0, 1, 2, 7, 8, 9}

vs list comprehension as above

print [x for x in item if x not in Z]

Out[38]: [0, 1, 1, 2, 7, 8, 9]

or filter function:

filter(lambda x: x not in Z, item)

Out[38]: [0, 1, 1, 2, 7, 8, 9]

Upvotes: 23

jspcal
jspcal

Reputation: 51904

list1 = [1,2,3,4]; list2 = [0,3,3,6]

print set(list2) - set(list1)

Upvotes: 12

Mark
Mark

Reputation: 108537

You are reassigning item to the values in z as you iterate through z. So the first time in your for loop, item = 0, next item = 1, etc... You are never checking one list against the other.

To do it very explicitly:

>>> item = [0,1,2,3,4,5,6,7,8,9]
>>> z = [0,1,2,3,4,5,6,7]
>>> 
>>> for elem in item:
...   if elem not in z:
...     print elem
... 
8
9

Upvotes: 1

Josh Wright
Josh Wright

Reputation: 2505

Your code is a no-op. By the definition of the loop, "item" has to be in Z. A "For ... in" loop in Python means "Loop though the list called 'z', each time you loop, give me the next item in the list, and call it 'item'"

http://docs.python.org/tutorial/controlflow.html#for-statements

I think your confusion arises from the fact that you're using the variable name "item" twice, to mean two different things.

Upvotes: 3

ntownsend
ntownsend

Reputation: 7630

No, z is undefined. item contains a list of integers.

I think what you're trying to do is this:

#z defined elsewhere
item = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in item:
  if i not in z: print i

As has been stated in other answers, you may want to try using sets.

Upvotes: 4

Doc Brown
Doc Brown

Reputation: 20044

If you run a loop taking items from z, how do you expect them not to be in z? IMHO it would make more sense comparing items from a different list to z.

Upvotes: 4

sberry
sberry

Reputation: 132018

>>> item = set([0,1,2,3,4,5,6,7,8,9])
>>> z = set([2,3,4])
>>> print item - z
set([0, 1, 5, 6, 7, 8, 9])

Upvotes: 4

Antony Hatchkins
Antony Hatchkins

Reputation: 33994

>> items = [1,2,3,4]
>> Z = [3,4,5,6]

>> print list(set(items)-set(Z))
[1, 2]

Upvotes: 73

Related Questions