Python: Concatenate list of lists in the algebraic way

Question

In maths, when you have two sets of words A={foo,bar} and B={x,y}, then the algebraic (or each-to-each) product is AB={foox,fooy,barx,bary}. I would like a similar thing in Python. Given two sets of words (= list of lists):

A = [ [0,1], [2,3] ]
B = [ [4,5], [6,7] ]

I would like to concatenate them each-to-each:

AB = [ [0,1,4,5], [0,1,6,7], [2,3,4,5], [2,3,6,7] ]

That itself is not so difficult, it can be done with product:

AB = [ a+b for (a,b) in itertools.product(A,B) ]

However, I have a list of "sets" (aka, list of lists of lists)

A = [ [0,1], [2,3] ]
B = [ [4,5], [6,7] ]
C = [ [4,5], [6,7] ]
SETS = [A,B,C]

Now I can do manually

ABC = [ a+b+c for (a,b,c) in itertools.product(A,B,C) ]

But I can't do that if I have 20 sets to concatenate. So, how to write a definition of ABC that would use only SETS and would accept any size of it?

Answer 1

ABC = [ sum(z, []) for z in itertools.product(*SETS) ]

product(*SETS) basically does product(A, B, C). The technical term is argument unpacking.

sum(z, []) basically does a + b + c + [].

EDIT:

As smart people said in the comments sum isn't a best way to join a list of lists. O(n^2) time complexity is pretty brutal.

To quote a documentation:

For some use cases, there are good alternatives to sum(). The preferred, fast way to concatenate a sequence of strings is by calling ''.join(sequence). To add floating point values with extended precision, see math.fsum(). To concatenate a series of iterables, consider using itertools.chain().

That's better:

from itertools import chain, product
ABC = [ list(chain(*z)) for z in product(*SETS) ]

or, if two argument unpackings is one argument unpacking too many:

ABC = [ list(chain.from_iterable(z)) for z in product(*SETS) ]

or, if you're into map:

ABC = map(list, map(chain.from_iterable, product(*SETS)))

Answer 2

Using argument unpacking, you can abstract over the number of sets: itertools.product(*SETS). Furthermore, you can define a helper function to concatenate a variable number of lists (efficiently):

def concat(seqs):
    result = []
    for seq in seqs:
        result.extend(seq)
    return result

In summary: [concat(prod) for prod in itertools.product(*SETS)]

Answer 3

First, use the * operator to unpack SETS for the itertools.product() function argument.

    itertools.product(*SET)

Then using import operator, concatenate the result from that:

    product = [ reduce(operator.add, tuple) for tuple in itertools.product(*SET) ]

This works because if the tuple variable is ([0,1], [4,5], [8,9]), reduce(operator.add, tuple) still gives you [0,1,4,5,8,9].