通过列表列表递归“所有路径” - Python

Question

一个特殊的问题，给定一个列表列表（这里最多嵌套一层）：

[['a', 'b'], 'c', ['d', 'e'], ['f', 'g'], 'h']

..找到所有长度与给定列表相同的列表，并包含来自子列表的元素的所有可能组合，给定子列表的 1 个元素与原始子列表位于相同的位置（甚至很难用文字表达）。也就是说，找到这个：

['a', 'c', 'd', 'f', 'h']
['a', 'c', 'd', 'g', 'h']
['a', 'c', 'e', 'f', 'h']
['a', 'c', 'e', 'g', 'h']
['b', 'c', 'd', 'f', 'h']
['b', 'c', 'd', 'g', 'h']
['b', 'c', 'e', 'f', 'h']
['b', 'c', 'e', 'g', 'h']

现在，我找到了解决方案，但对我来说并不令人满意：

def all_paths(s, acc=None, result=None):
    # not using usual "acc = acc or []" trick, because on the next recursive call "[] or []" would be
    # evaluated left to right and acc would point to SECOND [], which creates separate accumulator 
    # for each call stack frame
    if acc is None:
        acc = []
    if result is None:
        result = []
    head, tail = s[0], s[1:]
    acc_copy = acc[:]
    for el in head:
        acc = acc_copy[:]
        acc.append(el)
        if tail:
            all_paths(tail, acc=acc, result=result)
        else:
            result.append(acc)
    return result

如您所见，它涉及复制累加器列表两次，原因很明显，如果 .append() 或 .extend() 方法在递归堆栈中被调用，累加器将被修改，因为它是通过标签传递的（在官方行话中共享） ？）。

我试图编写 pop()s 和 append()s 相关数量的累加器项目的解决方案，但无法正确解决：

def all_p(s, acc=None, result=None, calldepth=0, seqlen=0):
    if acc is None:
        acc = []
    if result is None:
        seqlen = len(s)
        result = []
    head, tail = s[0], s[1:]
    for el in head:
        acc.append(el)
        if tail:
            all_p(tail, acc=acc, result=result, calldepth=calldepth+1, seqlen=seqlen)
        else:
            result.append(acc[:])
            print acc
            for i in xrange(1+seqlen-calldepth):
                acc.pop()
    return result

结果：

['a', 'c', 'd', 'f', 'h']
['a', 'c', 'd', 'g', 'h']
['a', 'c', 'd', 'e', 'f', 'h']
['a', 'c', 'd', 'e', 'g', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'f', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'g', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'e', 'f', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'e', 'g', 'h']
['a', 'c', 'd', 'f', 'h']
['a', 'c', 'd', 'g', 'h']
['a', 'c', 'd', 'e', 'f', 'h']
['a', 'c', 'd', 'e', 'g', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'f', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'g', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'e', 'f', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'e', 'g', 'h']

显然，这是因为这里的深度优先递归会在调用链中上下跳跃，我无法正确获取 pop() 的数量来微调累加器列表。

我确实意识到这几乎没有实际收益，因为复制列表是 O(n) 而从列表中弹出 k 个项目是 O(k)，所以这里没有太大区别，但我很好奇这是否可以实现。

（背景：我正在重做电话代码基准，http ://page.mi.fu-berlin.de/prechelt/phonecode/，这是找到所有单词的部分，但电话号码的每个部分都可以映射到几个字，像这样：

... '4824': ['fort', 'Torf'], '4021': ['fern'], '562': ['mir', 'Mix'] ...

所以我需要通过选定的匹配单词和/或数字列表找到所有可能的“路径”，对应于给定的电话号码）

问题、要求：

1. 不复制累加器的版本可以修复吗？

2. 有没有使用 itertools 模块的解决方案？

3. 任何其他更好的方法来解决这个特定问题？像非递归解决方案，更快的解决方案，更少的内存密集型？

是的，我知道这是一大堆问题，但如果有人解决了其中的非空子集，我将不胜感激。:-)

Answer 1

有没有使用 itertools 模块的解决方案？

是的，使用itertools.product(). 这对于您的特定示例来说已经足够了...

>>> import itertools
>>> l = [['a', 'b'], 'c', ['d', 'e'], ['f', 'g'], 'h']
>>> for i in itertools.product(*l): print list(i)
['a', 'c', 'd', 'f', 'h']
['a', 'c', 'd', 'g', 'h']
['a', 'c', 'e', 'f', 'h']
['a', 'c', 'e', 'g', 'h']
['b', 'c', 'd', 'f', 'h']
['b', 'c', 'd', 'g', 'h']
['b', 'c', 'e', 'f', 'h']
['b', 'c', 'e', 'g', 'h']

...但正如 DSM 在评论中指出的那样，它仅适用于您的示例使用单字符字符串，它们是长度为 1 的序列对象。如果总是这样，你可以像这样表达列表......

['ab', 'c', 'de', 'fg', 'h']

但是，在一般情况下，您可能希望确保所有列表项都是具有以下内容的序列...

>>> l = [None, int, 0, 'abc', [1, 2, 3], ('a', 'b')]
>>> for i in itertools.product(*[i if isinstance(i, (list, tuple)) else [i] for i in l]): print list(i)
[None, <type 'int'>, 0, 'abc', 1, 'a']
[None, <type 'int'>, 0, 'abc', 1, 'b']
[None, <type 'int'>, 0, 'abc', 2, 'a']
[None, <type 'int'>, 0, 'abc', 2, 'b']
[None, <type 'int'>, 0, 'abc', 3, 'a']
[None, <type 'int'>, 0, 'abc', 3, 'b']

任何其他更好的方法来解决这个特定问题？像非递归解决方案，更快的解决方案，更少的内存密集型？

任何解决方案都可能必须以某种方式使用递归，如果不在堆栈上，则在堆上。