Generate All Replacements for List of Lists

February 2, 2023

I’m building an application in Python where I need to define the following sort of function:

generate_replacements(['a', 'b', ['c', ['e', 'f']]], 1)

The expected output is all possible versions of the input list where just one element has been replaced

[
[1, 'b', ['c', ['e', 'f']]],
['a', 1, ['c', ['e', 'f']]],
['a', 'b', 1],
['a', 'b', [1, ['e', 'f']]],
['a', 'b', ['c', 1]],
['a', 'b', ['c', [1, 'f']]],
['a', 'b', ['c', ['e', 1]]]
]

I can see that recursion is the way to go, but I’m really stuck figuring out how to even best start this.

>Solution :

You can generate the replacements from the list, then if you notice you are replacing a list, also pass that list back through the function recursively. This is made a bit simpler if you use a generator:

def generate_replacements(l, rep):
    for i in range(len(l)):
        yield l[0:i] + [rep] + l[i+1: ]
        if isinstance(l[i], list):
            yield from (l[0:i] + [rec] + l[i+1: ] 
                        for rec in generate_replacements(l[i], rep))


list(generate_replacements(['a', 'b', ['c', ['e', 'f']]], 1))

This give:

[[1, 'b', ['c', ['e', 'f']]],
 ['a', 1, ['c', ['e', 'f']]],
 ['a', 'b', 1],
 ['a', 'b', [1, ['e', 'f']]],
 ['a', 'b', ['c', 1]],
 ['a', 'b', ['c', [1, 'f']]],
 ['a', 'b', ['c', ['e', 1]]]]