Python – How to Avoid Nested Loops for String Concatenation with Pythonic Approach

python

I want to find all 5-digit strings, for which

  • the first three digits are in my first list,
  • the second trough fourth are in my second and
  • the third to fifth are in my last list:
l0=["123","567","451"]
l1=["234","239","881"]
l2=["348","551","399"]

should thus yield: ['12348', '12399'].

I have therefore written a funciton is_successor(a,b) that tests if a and b overlap:

def is_successor(a:str,b:str)->bool:
    """tests if strings a and b overlap"""
    return a[1:]==b[:2]

I can then achieve my goal by writing this nested loop/check structure, that basically appends back to front strings and resulting in all valid strings:

pres=[]
for c in l2:
    for b in l1:
        if is_successor(b,c):
            for a in l0:
                if is_successor(a,b):
                    pres.append(a[0]+b[0]+c)

pres
  • I know I could write it as a list comprehension, but for my original data i have more nested lists and i loose readability even in a list comprehension.
  • I start from l2 -> l0 because in my original data the lists become longer, the lower the index and thus I can filter out more cases early this way.
  • A single loop trough all combinations of l0,l1,l2 and checking the succession of all items a,b,c simultaneously would work but it test way more unnecessary combinations than my current construct does.

Question:

How can this nested loop and conditional checking call be astracted? Is there a pythonic way to capture the repetition of for -> is_successor()?

A larger input might be:


primes=[2,3,5,7,11,13,17]

lsts=[
    [
        str(j).zfill(3) 
        for j in range(12,988) 
        if not j%prime
    ] 
    for prime in primes
]

Best Answer

You can rewrite it to work on arbitrary amount of lists in the following way:

First, put elements of the last list into sub lists with 1 element (this streamlines further processing)

ps = [[c] for c in l2]
print(ps) # [['348'], ['551'], ['399']]

Next, for each of the remaining lists check what elements match to elements in ps and add them to the beggining of matching elements.

for l in [l1, l0]:
    ps = [[a] + p for a in l for p in ps if is_successor(a, p[0])]

print(ps) # [['123', '234', '348'], ['123', '239', '399']]

Now assemble the final string back from lists

pres = []
for p in ps:
    pres.append(p[0]) # add entire element from l0
    for el in p[1:]:
        pres[-1] += el[-1] # add last character from following lists

print(pres) # ['12348', '12399']

As the only places we reference input lists directly is for l in [l1, l0]: and creation of initial list from a last one, this will work for any number of lists if those lines are updated.

Related Question