Combinations of elements of different tuples in a list

Question

I have a list of tuples: [(1, 2, 3), (2, 4)](the length of the list and tuples can vary), and I want to get all combinations containing at least one element from each tuple in the list, but also those combinations that contain more.

So, the result should be in this example:
[[1, 2, 3, 2, 4], [1, 2, 2, 4], [2, 3, 2, 4], [1, 2, 4], [2, 2, 4], [3, 2, 4], [1, 2, 3, 2], [1, 2, 3, 4], [1, 2, 2], [1, 2, 4], [2, 3, 2], [2, 3, 4], [1, 2], [1, 4], [2, 2], [2, 4], [3, 2], [3, 4]]

The smallest result should contain the number of elements equal to the number of tuples in the source list, the largest should contain all the elements present in the tuples.

The order of the elements does not matter, and duplicates should be ultimately eliminated (therefore, [1, 2, 3, 2, 4] = [1, 2, 3, 4]and should be the result only once, similarly [3, 2] = [2, 3], etc.), but I was thinking about sorting and / or eliminating duplicates after creating the entire list.

What is the best way to do this? Honestly, I don’t even know how to get started ...

Answer 1

You want the Cartesian product of the sets of elements in L - unless all of them are empty. One way is to simply leave the empty elements when we build the poweret.

from itertools import product, combinations, chain
L = [(1, 2, 3), (2, 4)]
def powerset(iterable):
    "powerset minus the empty element"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1))

print [list(chain.from_iterable(c)) for c in product(*(powerset(x) for x in L))]

prints

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

Answer 2

Let two lists be indicated by Xand Y, and their lengths indicated by |X|and |Y|.

poweret (X) has a length 2^|X|, and the power set (Y) has a length 2^|Y|.

, 2^(|X|+|Y|). , ( ), . , . , .

, , . X Y , XY, XY 2^(|XY|). 2^(|X|+|Y|), X Y . , 2 .

, X Y. , . , , .

---

import itertools as IT

def powerset(iterable, reverse=False, rvals=None):
    """powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"""
    s = list(iterable)
    N = len(s)
    if rvals is None:
        rvals = range(N, -1, -1) if reverse else range(N + 1)
    return IT.chain.from_iterable(
        IT.combinations(s, r) for r in rvals)

def powerreps(X, Y):
    """
    Return powerset with at least one representative from X and Y
    """
    XY = set(X).union(Y)
    for rep in powerset(XY, rvals=range(2, len(XY))):
        if any(x in rep for x in X) and any(y in rep for y in Y):
            yield rep

X, Y = (1, 2, 3), (2, 4)
print(list(powerreps(X, Y)))

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