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

原始数据是个二维 list，list 的长度不定，里面的每个子项长度也不定，类似下面这样情况：
original_list = [['a','b','c'],['@','#','$','%'],['1','2'],...]
现在需要把所有的子项遍历一遍(每个子项取一个值生成一个新的 list，把所有的情况都排列组合出来)，得到类似这样的结果：
target_list = [['a','@','1',...],['a','@','2',...],['a','#','1',...],['a','#','2',...],...]

请问如何优雅的实现？

List

子项

子项遍历

历子项

17 条回复 2018-02-04 02:29:57 +08:00

rrfeng

2018-01-31 18:15:07 +08:00 via Android

itertools.product ？

tempdban

2018-01-31 18:18:50 +08:00

@rrfeng 哈哈哈哈莫名喜感

frank065

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

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

2018-01-31 18:43:17 +08:00

@tempdban 哪里好笑了？
@frank065 那是因为你没仔细看 product 怎么用

最简单的办法可能是这样：itertools.product(*original)
不保证有没有问题……毕竟不太常写 python

frank065

2018-01-31 19:11:55 +08:00 via iPhone

@yangzhezjgs 这样写运行没问题，但是如果不知道原始 list 有多少子项，就没法这样操作
@rrfeng itertools.product(*original) 这样写没问题

谢谢各位 :)

Hzzone

2018-01-31 19:15:40 +08:00 via iPhone

先从最外层取两个，再最内层取一个，可以用下标
itertools.combinations

tjbwyk

2018-01-31 19:20:53 +08:00 via Android

最先想到的是深搜。。

rrfeng

2018-01-31 19:26:06 +08:00 via Android

总感觉用 *展开其实有点 trick 并且不是很安全（可能 list 很大？）

有没有大佬分析一下？

nodekey

2018-01-31 19:28:27 +08:00

分治？

表示不是很会 python

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

2018-01-31 19:32:17 +08:00 via Android

排版醉了

frank065

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

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

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

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

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
})
}