Python实现笛卡尔乘积的几种方法「终于解决」

大家好，欢迎来到IT知识分享网。

引言：面试的时候面试官出的这道题，当时写的不是太好，面试结束后下来查了一下，发现大部分的博客都是使用工具包来实现，而且大部分的博客内容还都完全一样，连数字都没有变，找了半天也没找到几个有用的博客。其实这也是现在大部分博客的风气，互相抄袭，没有一点自己的思考内容，我都不明白写这样的博客有什么意义。所以自己打算实现一个不使用工具包来解决的方法，于是在别人的博客帮助下，实现了用回溯法来解决笛卡尔乘积，下面是总结一下解决这个问题的几个方法：

1、工具包

from itertools import product
res = list(product(['a','b'],['c'],['d','e','g']))
print(res)

IT知识分享网

2、递归生成器，此方法参考的是 Python 用递归生成器计算笛卡尔积 | LFhacks.com 这个博客的内容，直接代码复制过来了

IT知识分享网def combi(seq):
    if not seq:
        yield []
    else:
        for element in seq[0]:
            for rest in combi(seq[1:]):
                yield [element] + rest

用下面的代码测试

n=[[1,2,3],[4],[5,6,7]]
print list(combi(n))

运行方式为：

IT知识分享网拆出第一个序列，得到1,2,3
对于1                      （暂存结果[1]）
拆出第2个序列，得到4
    对于4                      （暂存结果[1, 4]）
    拆出第3个序列，得到5,6,7
        对于5                       （暂存结果[1, 4, 5]）
        拆出第4个序列（空），得到（空）       
        把5加到（空）前面，返回结果    （返回暂存结果[1, 4, 5]）
        对于6                       （暂存结果[1, 4, 6]）
        拆出第4个序列（空），得到（空）        
        把6加到（空）前面，返回结果    （返回暂存结果[1, 4, 6]）
        对于7                       （暂存结果[1, 4, 7]）
        拆出第4个序列（空），得到（空）       
        把7加到（空）前面，返回结果    （返回暂存结果[1, 4, 7]）

3、回溯法实现

arr = [['a','b],['c'],['d','e','g']]
res = []
layer = len(arr)
def func(arr,index,temp,layer):
    if len(temp)==layer:
        res.append(temp[:])
    else:
        if not arr[index]:
            layer -= 1
            func(arr, index + 1, temp,layer)
        else:
            for i in range(len(arr[index])):
                temp.append(arr[index][i])
                func(arr,index+1,temp,layer)
                temp.pop()

func(arr,0,[],layer)
print(res)

这里使用layer的原因是因为防止子列表出现空列表的情况，如果不会出现子列表是空列表的情况，可以在temp的长度等于arr的长度的时候，就把temp添加到结果集合里去

参考：算法系列——输出所有的笛卡尔积组合_BridgeGeorge的博客-CSDN博客_笛卡尔积组合