以深度优先搜索式的方式附加任意嵌套列表的元素，无需递归

Question

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

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

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

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

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

我的递归代码如下：

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']

以深度优先搜索式的方式附加任意嵌套列表的元素，无需递归

Append elements of an arbitrarily nested list in a depth first search-esque manner, without recursion

python

depth-first-search