Python 用递归生成器计算笛卡尔积

2014-06-26
本文发布至今已有8年零166天,可能不再适用,请谨慎对待。

本文介绍如何用 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$ 为:

123456789101112
$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]

以上这是第一次递归的分析结果,后面的过程与之类似。

捐助本站

为了保证阅读体验,本站不安放广告。但是,租用服务器和编写文章需要个人资金和时间的投入。

如果您觉得文章对您有用,请考虑捐助小站(金额不限),以期待更多原创文章。捐助记录

本站是个人网站,若无特别说明,文章均为原创,并采用 署名协议 CC-BY-NC 授权。
欢迎转载,惟请保留原文链接,且不得用于商业用途。