Most efficient way to join 6 sections end to end without 6 for loops

Question

I have 6 lists of lists (sections), sec1 through sec6. I want to join them in order to form one list.

Example:

sec1 = [[1,2,3],[4,5,6]]
sec2 = [[7,8,9], [6], [1,2]]

If I join these two sections, I should get:

sec_join = [[1,2,3,7,8,9], [1,2,3,6], [1,2,3,1,2], [4,5,6,7,8,9], [4,5,6,6], [4,5,6,1,2]]

Now I have 6 such sections and I want to join them accordingly.

Note: len(sec_join) = len(sec1)*len(sec2)....*len(sec6)

I can do this using 6 for loops

[[[[[[sec_join.append(x1 + x2 + x3 + x4 + x5 + x6) for x1 in sec1] for x2 in sec2] for x3 in sec3] for x4 in sec4] for x5 in sec5] for x6 in sec6]

But the above method is O($n^6$). Is it possible to do it in better time complexity?

Note: In my case, the elements of sec1...sec6 are tuples of integers and not integers and hence sorting could be messy.

Edit:

I understand it cant be done in better than O($n^6$) complexity. Still, are there any "pythonic" ways to do it faster other than 6 for loops & list comrehension? Using any library functions, etc?

You think it's possible to get a better time complexity than the result size? — Kelly Bundy, Jan 25 '22 at 21:10
https://stackoverflow.com/questions/533905/get-the-cartesian-product-of-a-series-of-lists — user3386109, Jan 25 '22 at 21:19

score 1 · Answer 1 · answered Jan 25 '22 at 21:19

Use itertools from the standard library:

from itertools import chain, product

sec1 = [[1,2,3],[4,5,6]]
sec2 = [[7,8,9], [6], [1,2]]

sec_join = [list(chain(*x)) for x in product(sec1, sec2)]

For all 6 do:

sec_join = [list(chain(*x)) for x in product(sec1, sec2, sec3, sec4, sec5, sec6)]

Kelly Bundy · Accepted Answer · 2022-01-25T22:06:38.357

I think list concatenation will be faster than going through chain.

sec_join = sec1
for sec in sec2, sec3, sec4, sec5, sec6:
    sec_join = [head + tail
                for head in sec_join
                for tail in sec]

Could likely be sped up further by combining in different ways, but I'd have to know the actual list sizes.

This might be fastest, minimizing the number of iterations if your lists are about the same size:

sec_join = sec6
for sec in sec5, sec4, sec3, sec2, sec1:
    sec_join = [head + tail
                for head in sec
                for tail in sec_join]

A little benchmark:

134 ms myrtlecat
 46 ms Kelly

Code (Try it online!):

from itertools import chain, product

sec1 = [[1,2,3],[4,5,6]]*3
sec2 = [[7,8,9], [6], [1,2]]*3

def Kelly(sec1,sec2,sec3,sec4,sec5,sec6):
  sec_join = sec6
  for sec in sec5, sec4, sec3, sec2, sec1:
    sec_join = [head + tail
                for head in sec
                for tail in sec_join]
  return sec_join

def myrtlecat(sec1,sec2,sec3,sec4,sec5,sec6):
  return [list(chain(*x)) for x in product(sec1, sec2, sec3, sec4, sec5, sec6)]

from timeit import *

args = sec1,sec2,sec1,sec2,sec1,sec2
expect = myrtlecat(*args)
result = Kelly(*args)
print(result == expect)
for a in expect, result: print(len(a))
for func in [myrtlecat, Kelly]*3:
  t = min(repeat(lambda: func(*args), number=1))
  print('%3d ms' % (t * 1e3), func.__name__)

Most efficient way to join 6 sections end to end without 6 for loops

2 Answers2