Pythonic way to find all the different intersections and differences between two lists of arrays

Question

This is the generalization of a previous question of mine. I need to find all the intersections and differences between two lists of different arrays. There are no intersections within the arrays of any of the lists, only between the arrays in different lists.

The expected result for the next example

x = [np.array([0, 6, 7, 10]), np.array([1, 2, 5, 9])]
y = [np.array([ 7, 10]), np.array([8]), np.array([0, 3, 4, 5])]

should be

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

Any suggestion? Thanks in advance!

What should be the decomposition between (0,6,7,10) and (7,10)? Shouldn't it be (0,6) (7,10) and ( )? The third set should be empty or nothing since there is no unintersecting part in (7,10). — Mercury, May 19 '20 at 15:31
Between (0,6,7,10) and (7,10) the function should return (0,6) and (7,10), but in this particular case, (0, 6) is further decomposed again into (0) and (6) because 0 is present in (0, 3, 4, 5), but 6 is not present there. — Jorge, May 19 '20 at 15:38
I see. So the decomposition should happen till there are no intersecting sets remaining? — Mercury, May 19 '20 at 15:40
What if there are no intersection in u and v, but intersections are present within u? Like u=[ (1,10),(2,10) ] and v=[(3,4),(5,6)]. There isn't any intersection between any pair of arrays from u and v. So should the answer be (1,10),(2,10)(3,4)(5,6)? Or should it be (1),(10),(2),(3,4)(5,6)? — Mercury, May 19 '20 at 17:48
There are no intersections within arrays in u, or within the arrays in v. I thought about adding it as an assert code line, but I will add it in the main text. — Jorge, May 19 '20 at 17:58

score 1 · Accepted Answer · edited May 20 '20 at 07:19

There is no point to separate arguments, the result will be the same as you unite x and y. So you have set of sets and try to find separate pieces. To find them you can iterate through all elements and remember at which sets this value was encountered. Then if 2 elements have exactly the same set of sets (say they both met at second and forth sets) we return this elements as united group.

from collections import defaultdict


def pythonic(s):
    """
    >>> pythonic([[0, 6, 7, 10], [1, 2, 5, 9], [7, 10], [0, 3, 4, 5]])
    [[0], [6], [7, 10], [1, 2, 9], [5], [3, 4]]
    >>> pythonic([[7, 10], [8], [0, 3, 4, 5], [0, 6, 7, 10], [1, 2, 5, 9]])
    [[7, 10], [8], [0], [3, 4], [5], [6], [1, 2, 9]]
    >>> pythonic([[0, 1, 4, 5], [1, 2, 3, 4], [3, 4, 5, 6]])
    [[0], [1], [4], [5], [2], [3], [6]]
    """
    all_elements = defaultdict(list)
    for i, ss in enumerate(s):
        for elem in ss:
            all_elements[elem].append(i)
    reversed = defaultdict(list)
    for k, v in all_elements.items():
        reversed[frozenset(v)].append(k) # or tuple can be used but "frozenset" feels "safer"
    return list(reversed.values())

Thank you so much! I tested it and it seems to work very nicely. Yesterday I was looking some similar problems with defaultdict as an answer, I guess I still have a lot to learn. It is hard to express how much gratitude I feel for your help. — Jorge, May 19 '20 at 17:56

Pythonic way to find all the different intersections and differences between two lists of arrays

1 Answers1