16

Given list a = [1, 2, 2, 3] and its sublist b = [1, 2] find a list complementing b in such a way that sorted(a) == sorted(b + complement). In the example above the complement would be a list of [2, 3].

It is tempting to use list comprehension:

complement = [x for x in a if x not in b]

or sets:

complement = list(set(a) - set(b))

However, both of this ways will return complement = [3].

An obvious way of doing it would be:

complement = a[:]
for element in b:
    complement.remove(element)

But that feels deeply unsatisfying and not very Pythonic. Am I missing an obvious idiom or is this the way?

As pointed out below what about performance this is O(n^2) Is there more efficient way?

Improve this question
8
  • 1
    you can create a list comprehension from the *unsatisfying option. Would that make it *satisfying? Commented Feb 16, 2017 at 12:17
  • Don't see how just post it ! Commented Feb 16, 2017 at 12:19
  • 5
    I do not really see what is that much un-Pythonic about it. It is not completely declarative, but still very readable. I would be more concerned with performance, since this will run in O(n^2), which is not very nice... Commented Feb 16, 2017 at 12:19
  • @JanHak just replace the last two lines with an unassigned [complement.remove(element) for element in b] but as @Willem says, it is not about the looks. This is almost a *hack of the list comprehension since we are not creating a list but simply using the syntax to do something else Commented Feb 16, 2017 at 12:23
  • 1
    Relevant: stackoverflow.com/questions/8106227/… Commented Feb 16, 2017 at 13:12

5 Answers 5

Reset to default
17

The only more declarative and thus Pythonic way that pops into my mind and that improves performance for large b (and a) is to use some sort of counter with decrement:

from collections import Counter

class DecrementCounter(Counter):

    def decrement(self,x):
        if self[x]:
            self[x] -= 1
            return True
        return False

Now we can use list comprehension:

b_count = DecrementCounter(b)
complement = [x for x in a if not b_count.decrement(x)]

Here we thus keep track of the counts in b, for each element in a we look whether it is part of b_count. If that is indeed the case we decrement the counter and ignore the element. Otherwise we add it to the complement. Note that this only works, if we are sure such complement exists.

After you have constructed the complement, you can check if the complement exists with:

not bool(+b_count)

If this is False, then such complement cannot be constructed (for instance a=[1] and b=[1,3]). So a full implementation could be:

b_count = DecrementCounter(b)
complement = [x for x in a if not b_count.decrement(x)]
if +b_count:
    raise ValueError('complement cannot be constructed')

If dictionary lookup runs in O(1) (which it usually does, only in rare occasions it is O(n)), then this algorithm runs in O(|a|+|b|) (so the sum of the sizes of the lists). Whereas the remove approach will usually run in O(|a|×|b|).

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Image
Thanks @Willem great answer learned something! I had to wrap my head around the side-effect of calling the method decrement - creative!
Image
@Hironsan: That's why (it is even in boldface), the answer says: "such complement exists.". If you swap a and b, such complement does not exists.
Image
@Hironsan: I included a test which will raise a ValueError in case no such complement can be constructed.
Image
... why bool(+b_count)? Isn't that equivalent to simply b_count in the boolean context? AFAIK +counter == counter if isinstance(counter, Counter), so the + does literally nothing, except causing confusion, and bool again... it's what python does anyway when checking the truthiness of a value.
Image
For a counter, the + removes the negative and zero Countdown. The bool can indeed be omitted.
|
5

In order to reduce complexity to your already valid approach, you could use collections.Counter (which is a specialized dictionary with fast lookup) to count items in both lists.

Then update the count by substracting values, and in the end filter the list by only keeping items whose count is > 0 and rebuild it/chain it using itertools.chain

from collections import Counter
import itertools

a  = [1, 2, 2, 2, 3]
b = [1, 2]

print(list(itertools.chain.from_iterable(x*[k] for k,x in (Counter(a)-Counter(b)).items() if x > 0)))

result:

[2, 2, 3]
Improve this answer

5 Comments

Image
what is Counter order ? is it O(n)?
Image
But won't this result in the fact that if complement should have two twos, it will only have one? like a=[1,2,2,2], b=[1,2]... Here the condition is that if x > 0, you only emit it once.
Image
Counter is a dictionary: lookup is less that O(n)
Image
counting element in a list is less than O(n) using Counter?!
Image
not counting, lookup. You have to analyse the data, for that you have to run through it once. But after that, lookup is fast.
2

O(n log n) 

a = [1, 2, 2, 3]
b = [1, 2]
a.sort()
b.sort()

L = []
i = j = 0
while i < len(a) and j < len(b):
    if a[i] < b[j]:
        L.append(a[i])
        i += 1
    elif a[i] > b[j]:
        L.append(b[j])
        j += 1
    else:
        i += 1
        j += 1

while i < len(a):
    L.append(a[i])
    i += 1

while j < len(b):
    L.append(b[j])
    j += 1

print(L)
Improve this answer

1 Comment

Image
If I swap a and b, it has no effect :)
2

If the order of elements in the complement doesn't matter, then collections.Counter is all that is needed:

from collections import Counter

a = [1, 2, 3, 2]
b = [1, 2]

complement = list((Counter(a) - Counter(b)).elements())  # complement = [2, 3]

If the order of items in the complement should be the same order as in the original list, then use something like this:

from collections import Counter, defaultdict
from itertools import count

a = [1,2,3,2]
b = [2,1]

c = Counter(b)
d = defaultdict(count)

complement = [x for x in a if next(d[x]) >= c[x]]  # complement = [3, 2]
Improve this answer

Comments

1

Main idea: if the values are not unique, make them unique

def add_duplicate_position(items):
    element_counter = {}
    for item in items:
        element_counter[item] = element_counter.setdefault(item,-1) + 1
        yield element_counter[item], item
    
assert list(add_duplicate_position([1, 2, 2, 3])) == [(0, 1), (0, 2), (1, 2), (0, 3)]

def create_complementary_list_with_duplicates(a,b):
    a = list(add_duplicate_position(a))
    b = set(add_duplicate_position(b))
    return [item for _,item in [x for x in a if x not in b]]
  
a = [1, 2, 2, 3]
b = [1, 2]
assert create_complementary_list_with_duplicates(a,b) == [2, 3]
Improve this answer

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.