本文介绍如何用 Python 实现向量的笛卡尔积（或者叫外积）。一个方法是使用内置函数，另一个方法使用递归生成器实现。
笛卡尔积的含义
有 $N$ 个向量，按固定顺序从每个向量中取出一个元素排列成新的向量，所有新的向量的集合，就是这 $N$ 个向量的笛卡尔积。比如有三个向量 $A,B,C$：
| $A$ | $B$ | $C$ |
|---|---|---|
| $a_1$ | $b_1$ | $c_1$ |
| $a_2$ | $b_2$ | $c_2$ |
| $a_3$ |
则 $A,B,C$ 三个向量的笛卡尔积 $A \times B \times C$ 为：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| $a_1$ | $a_1$ | $a_1$ | $a_1$ | $a_2$ | $a_2$ | $a_2$ | $a_2$ | $a_3$ | $a_3$ | $a_3$ | $a_3$ |
| $b_1$ | $b_1$ | $b_2$ | $b_2$ | $b_1$ | $b_1$ | $b_2$ | $b_2$ | $b_1$ | $b_1$ | $b_2$ | $b_2$ |
| $c_1$ | $c_2$ | $c_1$ | $c_2$ | $c_1$ | $c_2$ | $c_1$ | $c_2$ | $c_1$ | $c_2$ | $c_1$ | $c_2$ |
从排列知识可知，笛卡尔积的元素个数是原来 $N$ 个向量个数之积 $(3 \times 2 \times 2= 12)$
下面使用 Python 的两种方法求向量的笛卡尔积。
内置函数 product( )
Python内置的 itertools.product()函数 可以得到N个向量的笛卡尔积，例如：
from itertools import product
list(product([1,2,3],[4],[5,6,7]))
# [(1, 4, 5), (1, 4, 6), (1, 4, 7), (2, 4, 5), (2, 4, 6),\
# (2, 4, 7), (3, 4, 5), (3, 4, 6), (3, 4, 7)]
product()函数 返回一个生成器，它的等效代码为：
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)
生成器思路
递归的思路就像剥洋葱一样，尽管我们不知道一颗洋葱有几层，但是只要坚持剥下去，就一定能剥到最里层。
我们把剥洋葱的原则，描述为
def 剥(任意一颗洋葱)
函数的定义应该是下面这样的：
def 剥(洋葱):
如果 洋葱剥没了:
什么也给不了
否则:
剥去最外层
剥(剩下的洋葱)
对于无论多厚的一颗洋葱，只要执行一次 剥( ) 函数，就能遍历每一层。
回到上面的笛卡尔积问题来，假如我们把函数命名为 笛卡尔积() ，它看起来应该是这样的：
def 笛卡尔积(序列):
如果 序列 为 空:
给出（yield）空序列
否则:
拆开第一个子序列，对于其中每个元素
把这个元素加在 笛卡尔积(剩下的序列) 的每一个结果 前面
给出（yield） 这个组合
把上面的中文翻译成python语言，就得到想要的递归生成器
用python语言实现递归生成器
实现笛卡尔积的递归生成器，具体代码为：
def combi(seq):
if not seq:
yield []
else:
for element in seq[0]:
for rest in combi(seq[1:]):
yield [element] + rest
用下面的语句测试，得到的结果和 product() 函数一样：
n=[[1,2,3],[4],[5,6,7]]
print list(combi(n))
应用举例
用combi( )函数处理下面这个向量集合：
[[1,2,3],[4],[5,6,7]]
我们看看如何运行的：
拆出第一个序列，得到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]）
上面的过程结束后，就得到了
[1, 4, 5], [1, 4, 6], [1, 4, 7]
以上这是第一次递归的分析结果，后面的过程与之类似。
如果您对本站内容有疑问或者寻求合作，欢迎 联系邮箱 。邮箱已到剪贴板