V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
frank065
V2EX  ›  Python

求教算法,二维 list 如何遍历子项生成新的 list?

  •  
  •   frank065 · 2018-01-31 18:07:10 +08:00 · 2836 次点击
    这是一个创建于 2248 天前的主题,其中的信息可能已经有所发展或是发生改变。
    原始数据是个二维 list,list 的长度不定,里面的每个子项长度也不定,类似下面这样情况:
    original_list = [['a','b','c'],['@','#','$','%'],['1','2'],...]
    现在需要把所有的子项遍历一遍(每个子项取一个值生成一个新的 list,把所有的情况都排列组合出来),得到类似这样的结果:
    target_list = [['a','@','1',...],['a','@','2',...],['a','#','1',...],['a','#','2',...],...]

    请问如何优雅的实现?
    17 条回复    2018-02-04 02:29:57 +08:00
    rrfeng
        1
    rrfeng  
       2018-01-31 18:15:07 +08:00 via Android
    itertools.product ?
    tempdban
        2
    tempdban  
       2018-01-31 18:18:50 +08:00
    @rrfeng 哈哈哈哈莫名喜感
    frank065
        3
    frank065  
    OP
       2018-01-31 18:38:22 +08:00
    @rrfeng 这个生成笛卡尔积元祖的方法是没错,但是我运行了一遍得到的结果貌似有问题?

    original = [['a','b','c'],['@','#','$','%'],['1','2']]
    for i in product(x for x in original):
    print(i)
    ------得到的结果-----
    (['a', 'b', 'c'],)
    (['@', '#', '$', '%'],)
    (['1', '2'],)
    yangzhezjgs
        4
    yangzhezjgs  
       2018-01-31 18:39:12 +08:00
    >>> from itertools import product
    >>> o = [['a','b','c'],['@','#','$','%'],['1','2']]
    >>> for m, n, f in product(o[0],o[1],o[2]):
    ... t.append([m,n,f])
    rrfeng
        5
    rrfeng  
       2018-01-31 18:43:17 +08:00
    @tempdban 哪里好笑了?
    @frank065 那是因为你没仔细看 product 怎么用

    最简单的办法可能是这样:itertools.product(*original)
    不保证有没有问题……毕竟不太常写 python
    frank065
        6
    frank065  
    OP
       2018-01-31 19:11:55 +08:00 via iPhone
    @yangzhezjgs 这样写运行没问题,但是如果不知道原始 list 有多少子项,就没法这样操作
    @rrfeng itertools.product(*original) 这样写没问题

    谢谢各位 :)
    Hzzone
        7
    Hzzone  
       2018-01-31 19:15:40 +08:00 via iPhone
    先从最外层取两个,再最内层取一个,可以用下标
    itertools.combinations
    tjbwyk
        8
    tjbwyk  
       2018-01-31 19:20:53 +08:00 via Android
    最先想到的是深搜。。
    rrfeng
        9
    rrfeng  
       2018-01-31 19:26:06 +08:00 via Android
    总感觉用 *展开其实有点 trick 并且不是很安全(可能 list 很大?)

    有没有大佬分析一下?
    nodekey
        10
    nodekey  
       2018-01-31 19:28:27 +08:00
    分治?

    表示不是很会 python
    tjbwyk
        11
    tjbwyk  
       2018-01-31 19:31:38 +08:00 via Android
    伪代码大概这个意思。。
    dfs(outer_list, current_result, ans)
    if outer_list == null
    ans.push_back(current_result)
    return
    end
    // loop over inner_list
    for item in *outer_list
    current_result.push_back(item)
    dfs(outer_list.next(), current_result, and)
    current_result.pop_back()
    end
    end
    tjbwyk
        12
    tjbwyk  
       2018-01-31 19:32:17 +08:00 via Android
    排版醉了
    frank065
        13
    frank065  
    OP
       2018-02-01 11:18:18 +08:00
    看了 itertools.product 的源代码,直接这样就能实现了:

    original = [['a','b','c'],['@','#','$','%'],['1','2']]
    target = [[]]
    for pool in original:
    ...target = [x+[y] for x in target for y in pool]
    xpresslink
        14
    xpresslink  
       2018-02-01 11:28:16 +08:00
    >>> from itertools import product
    >>> original = [['a','b','c'],['@','#','$','%'],['1','2']]
    >>> list(product(*original))
    [('a', '@', '1'), ('a', '@', '2'), ('a', '#', '1'), ('a', '#', '2'), ('a', '$', '1'), ('a', '$', '2'), ('a', '%', '1'), ('a', '%', '2'), ('b', '@', '1'), ('b', '@', '2'), ('b', '#', '1'), ('b', '#', '2'), ('b', '$', '1'), ('b', '$', '2'), ('b', '%', '1'), ('b', '%', '2'), ('c', '@', '1'), ('c', '@', '2'), ('c', '#', '1'), ('c', '#', '2'), ('c', '$', '1'), ('c', '$', '2'), ('c', '%', '1'), ('c', '%', '2')]

    如果 original 中的 list 元素量大,product 是个生成器,要用 for 去调用,不然内存爆菊。
    psychoo
        15
    psychoo  
       2018-02-01 15:38:45 +08:00
    用深搜写的……
    original_list = [['a','b','c'],['@','#','$','%'],['1','2'],['1','2','8']]
    target_list = []
    def dfs(n,i,str0):
    str1 = []
    for j in range(len(str0)):
    str1.append(str0[j])
    str1.append(original_list[n][i])
    if(n == len(original_list) - 1):
    target_list.append(str1)
    else:
    for j in range(len(original_list[n+1])):
    dfs(n+1,j,str1)
    for j in range(len(original_list[0])):
    dfs(0,j,[])
    print(target_list)
    2gua
        16
    2gua  
       2018-02-03 23:47:53 +08:00
    lst = [['a', 'b', 'c'], ['@', '#', '$', '%'], ['1', '2']]

    1.
    import itertools
    [list(i) for i in itertools.product(*lst)]

    2.
    def cross(lst):
    def swim(l, t, res):
    if len(l) == 0:
    res += [t]
    return
    for i in l[0]:
    swim(l[1:], t + [i], res)

    res = []
    swim(lst, [], res)
    return res
    WickedDogg
        17
    WickedDogg  
       2018-02-04 02:29:57 +08:00
    从微博过来的,贴个 js 实现吧,不过 python 应该更简单,因为 python 里面的有些方法工具感觉更强大
    function map(arr) {
    return arr.reduce((previous, current) => {
    var mapped = []
    previous.map(val1 => {
    current.map(val2 => {
    return Array.isArray(val1) ? mapped.push([...val1, val2]) : mapped.push([val1, val2])
    })
    })
    return mapped
    })
    }
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1769 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 16:34 · PVG 00:34 · LAX 09:34 · JFK 12:34
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.