python creates a complement to a list that holds duplicate values

Given list a = [1,2,2,3], the sublist b = [1,2] finds a list that completes b by sorting (a)== sorting (b complement). In the above example, the complement would be a list of [2,3].

It's tempting to use list parsing:

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

Or Settings:

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

However, both approaches will return complement = [3].

One obvious approach is:

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

However, the feeling was very unsatisfactory, and not very good. Did I miss a wise idiom?

As noted below, is there a more efficient way to have performance is O(n ^ 2)?

Only more declarative and therefore Pythonic approach would come to mind, and to mention that the performance of b(and a) is to use some sort of subtraction counter:

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 parsing:

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

Here we track the counts in b, for each element we look at whether it is part 1 of b_count. If this is the case, we reduce the counter and ignore the element. Otherwise we add it to the completion. Note that this only works if we are confident that such a supplement exists.

After the complement is constructed, it can be checked whether the complement exists:

not bool(+b_count)

If this is False, then such a complement cannot be constructed (for example, a = [1] and b = [1,3]). So full implementation might 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 the dictionary lookup runs in O(1) (usually, but only in rare cases, O(n)), then the algorithm runs in O(| a | | b |) (therefore, the list). The deletion method is usually run in O(| a |×| b |).

conclusion