列表的排列组合

Question

假设我们有一个包含多个列表的列表。每个列表里面可以有任意数量的元素。例如 [[1,2,3,4],[2,3],[4,5,6,7],[1]]。我想生成这些列表的所有可能排列，其中每次排列只能从最里面的列表中选择一个元素。所以输出的结果会是 [1,2,4,1]、[1,3,4,1] 等等。

示例输入 = [[1,2],[3],[4]]
示例输出 = [[1,3,4],[2,3,4]]

我之前尝试过一些代码，但逻辑有问题。以下是我正在进行的代码，目前卡住了。我不知道该怎么继续下去。对于排列和组合，我不是很擅长。

我尝试的内容和上面描述的一样，只不过这里的最里面的元素是一些坐标。

[[[1,2],[2,4]],[[2,3],[4,2]],[[1,5]],[[3,3],[7,2],[5,6]]]

def perm(a,length):
    arr=[]
    k=0
    while (k<length):
        temp=[]
        for i in a:


a=[[[1,2],[2,4]],[[2,3],[4,2]],[[1,5]],[[3,3],[7,2],[5,6]]]
perm(a)

如果需要进一步的解释，请告诉我。任何帮助都非常感谢。

编辑

我希望能得到一个不使用 itertools 或其他类似 Python 模块的解决方案。我应该早点提到这一点。否则这是一个有效且非常方便的解决方案。

伪代码逻辑或简单的解决思路就可以，不用使用 Python 库。抱歉这么晚才补充这个细节。

Answer 1

我觉得下面这个递归版本比用列表推导式写的更容易理解，不过这可能只是个人喜好问题：

def cartesianProduct( *lists ) :
    if not lists : # nothing to do, yield empty tuple
        yield ()
    else : # let's do A x cartesianProduct( B x C x ... )
        for a in lists[0] : # each element of A
            for tup in cartesianProduct( *lists[1:] ) : # each tuple of ( B x C x ... )
                yield ( a, ) + tup # concatenate and yield 

list( product( 'AB', range(3), 'xy' ) ) == list( cartesianProduct('AB', range(3), 'xy') )

True 

Answer 2

你可以很简单地使用 itertools.product 来实现这个功能：

>>> from itertools import product
>>> list(product(*[[1,2],[3],[4]]))
[(1, 3, 4), (2, 3, 4)]
>>> list(product(*[[1,2,3,4],[2,3],[4,5,6,7],[1]]))
[(1, 2, 4, 1), (1, 2, 5, 1), (1, 2, 6, 1), (1, 2, 7, 1), 
 (1, 3, 4, 1), (1, 3, 5, 1), (1, 3, 6, 1), (1, 3, 7, 1), 
 (2, 2, 4, 1), (2, 2, 5, 1), (2, 2, 6, 1), (2, 2, 7, 1), 
 (2, 3, 4, 1), (2, 3, 5, 1), (2, 3, 6, 1), (2, 3, 7, 1), 
 (3, 2, 4, 1), (3, 2, 5, 1), (3, 2, 6, 1), (3, 2, 7, 1), 
 (3, 3, 4, 1), (3, 3, 5, 1), (3, 3, 6, 1), (3, 3, 7, 1), 
 (4, 2, 4, 1), (4, 2, 5, 1), (4, 2, 6, 1), (4, 2, 7, 1), 
 (4, 3, 4, 1), (4, 3, 5, 1), (4, 3, 6, 1), (4, 3, 7, 1)]

根据文档，这里有一个几乎等效的实现方式，不需要任何 import：

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)