以深度优先搜索的方式附加任意嵌套列表的元素，而不使用递归

Question

这个列表可以更深，也可以更浅，但是假设我有一个深度2的列表，如下所示：

a = [['a','b'],['c','d'],['e','f']]

我想编写一个函数f(a)，这样它将返回以下新列表：

['acef', 'adef', 'bcef', 'bdef']

本质上，我是在模仿深度优先搜索，其中列表是节点。我希望函数使用depth=n，其中n是任意整数。实现这一目标的最可行的方法是什么？你知道吗

我的递归代码如下：

def f(elems):
    curr, *rest = elems

    if not rest:
        return ''.join(curr)

    ret = [''.join(x + f(rest)) for x in curr]
    return ret

我该如何迭代求解这个问题？你知道吗

Answer 1

您可以使用itertools.product：

import itertools

def f(elems):
    *branches, leaves = elems
    for path in itertools.product(*branches):
        yield ''.join(itertools.chain(path, leaves))

a = [['a','b'],['c','d'],['e','f']]
print(list(f(a)))

这将提供：

['acef', 'adef', 'bcef', 'bdef']