首页 / PYTHON / 通过列表列表递归“所有路径” – Python

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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了通过列表列表递归“所有路径” – Python，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2967字，纯文字阅读大概需要5分钟。

内容图文

一个特殊的问题,给出一个列表列表(这里最多嵌套一个级别)：

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

正如你所看到的,它涉及复制累加器列表TWICE,原因很明显,如果.append()或.extend()方法被调用递归堆栈,累加器将被修改,因为它是通过标签传递的(在官方术语中共享) ？).

我试着煮出pop()的解决方案,并在累加器上附加()相关数量的项目,但无法正确：

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

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

问题,要求：

>可以修复不复制累加器的版本吗？
>有没有使用itertools模块的解决方案？
>任何其他更好的解决这个特殊问题的方法？像非递归解决方案,更快的解决方案,更少的内存密集型解决方案？

是的,我知道这是一大堆问题,但是如果有人解决了一些非空的问题,我将不胜感激.

内容总结

以上是互联网集市为您收集整理的通过列表列表递归“所有路径” – Python全部内容，希望文章能够帮你解决通过列表列表递归“所有路径” – Python所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/799786.html

来源：【匿名】