Get all possible combinations between two lists, including multiple connections

With

import itertools
l1 = [1,2,3,4]
l2 = [1,2,3,4]

x = itertools.product(l1, l2)
print(list(x))

I get the 16 possible individual combinations of the lists l1 and l2, [(1,1), (1,2), ... ] etc. Is there a way to also get combinations that ‘connect’ the lists in multiple ways? For example, I could have the following combinations [(1,1), (2,3)], [(1,3), (2,4), (3,2)], and [(1,2), (2,4), (3,3), (4, 1)].

Any help would be greatly appreciated.

Answer

You can view the problem as placing l1 balls, into l2 bins. See this answer on how to generate all those placements.

Because in your example, there are placements where some of the balls are absent from any bin, we can handle that by introducing an additional bin which we designate to be the trash bin (in other words, balls which end up in this bin, will be considered absent).