How to find the difference between each element of two list while one of them is not a nested list

Question

I'm trying to write an algorithtm that finds the difference between 2 lists, but one of them is not a nested list.

For example;

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

Expected output is

expected = [[2,3,4],[1,4],[1,2]]

So the goal is, find a-b1 where b1 is the each element in b one by one.

I tried to convert them to set(),frozenset() used filter() etc. but none of them was succesful. Either I got integer error or an output that is wrong(in my case).

My actual goal is writing this algorithm for Topology, where a is the set and b is the Topology on a. So I'm trying to write the closed set of that Topology.

In the real question, a and b are both sets where b is a nested set, but I realized working with lists is easier than sets to achieve my goal, but still none of the answers similar to my question(on stackoverflow) were not successful.

How can I find the closed set of a given set, or, find the difference of all elements in the list2 from list1, where list2 is a nested list and list1 is not.

Answer 1

When working with mathematical sets you should really use the provided set type in Python. I wrote your sets as Python sets:

a = {1,2,3,4}
b = [{1},{2,3},{3,4}]

Notice, that b is a list of sets; your topology on a. You can find differences between sets with the - operator (with two sets A and B, A-B is the same as the mathematical A\B):

res = [a-el for el in b]

Output:

In [11]: res
Out[11]: [{2, 3, 4}, {1, 4}, {1, 2}]

this is a list of the differences between the sets

EDIT Here is a way to transform your inputs in the way that you wanted:

First of all, prompt the user to write every set in parenthesis, to have a regular syntax, like for example: (1),(1,2),(2,3,4)

Now we need a regular expression to find the sets in the resulting string "(1),(1,2),(2,3,4)":

import re
inp_list = re.findall(r"(?:\(([\d,]+))", inp_string)

Now we can start with the solution mentioned above:

res = [{int(number) for number in inp.split(",")} for inp in inp_list]

To understand the regex, click here

Answer 2

I consider to write a custom method which returns the difference between two list:

def difference(w, z):
  [w.remove(x) for x in z if x in w]
  return w

Then use the method in a for loop:

res = []
for y in b:
  tmp = a[:]
  if not isinstance(y, list): y = [y]
  res.append(difference(tmp, y))

print(res)
#=> [[2, 3, 4], [1, 4], [1, 2]]

---

I don't know if it is useful but in this case:

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

The result is [[2, 2, 3, 4], [1, 2, 4], [1, 2, 2], [1, 2, 2, 3, 4]]

You can customize the method to better fit your needs.

Answer 3

You can do this with frozenset's or sets:

a = {1,2,3,4}    # normal set (mutable)
b = [1,frozenset({2,3}),frozenset({3,4})] # frozenset in list to keep ordering 

c = [ (a-x) if isinstance(x,set) else (a-set([x])) for x in b]

print(c)

Output:

[set([2, 3, 4]), set([1, 4]), set([1, 2])]

---

Unrolled list comp:

d = []
for top in b:
    d.append( a-top if isinstance(top,set) else a-set([top]) )

# d == c 

a-top is just the shorthand for set.difference. Here is a table of shorthands for sets (2.7 - still valid).

Answer 4

with your inputs:

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

now I'm converting a as a set

a = set(a)

then I'm performing set difference between a and elements of b, with just a test to see if the element is a simple value or a list. Convert back each element to list or use sorted to get increasing order.

result = [list(a-(set(be if isinstance(be,list) else [be]))) for be in b]

result:

[[2, 3, 4], [1, 4], [1, 2]]

Small variant, creating directly a set when passed a non-list:

result = [list(a-(set(be) if isinstance(be,list) else {be})) for be in b]

And non comprehension implementation

a = set(a)
result = []
for be in b:
    if isinstance(be,list):
        result.append(list(a-set(be)))
    else:
        result.append(list(a - {be}))

Only works with "flat" lists like your example