笛卡尔积

Python021

笛卡尔积,第1张

首先知道啥是笛卡尔积,百度百科中解释是这样的:

通俗理解就是一个集合中的所有元素与另外一个集合中的所有元素的所有组合。需要注意有先后顺序。

举个例子:

集合A={a,b}, B={0,1,2},则

A×B={(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}

B×A={(0, a), (0, b), (1, a), (1, b), (2, a), (2, b)}

再如:

集合A是所有声母,集合B是所有韵母。那么集合A与集合B的笛卡尔积就是所有的拼音组合。

python默认迭代器库 itertools 提供笛卡尔积计算函数 product 。

用法:

示例1:

计算姓氏“张、李”和名“一、二、三”所有搭配组合。

示例2:

当然不仅仅是两个集合,多个集合也同样可以。

比如字典的生成。

当然如果字典生成不需要有序的话,可以使用另外两个函数 permutations

和 combinations 。

两者的区别在于,如果几个集合的元素相同,但位置顺序不同,permutations记为不同集,而combinations记为同一集合,也就是permutations为有序集合combinations为无序集合。

在日常的工作学习中,我们肯定会遇到排列组合问题,比如,在5种颜色的球中,任意取3个,共有多少种组合方式,这也包括有放回和无放回抽样。

在python中,自带的排列组合函数,都在python的指导工具包itertools中。

product 笛卡尔积(有放回抽样排列)

permutations 排列(不放回抽样排列)

combinations 组合,没有重复(不放回抽样组合)

combinations_with_replacement 组合,有重复(有放回抽样组合)

python3中返回的为对象,可以通过迭代读取将值输出。

end

事实上,Python的标准语法是不支持跳出多重循环的,所以只能利用一些技巧,大概的思路有:写成函数、利用笛卡尔积、利用调试。

写成函数

在Python中,函数运行到return这一句就会停止,因此可以利用这一特性,将功能写成函数,终止多重循环,例如

def work():for i in range(10):for j in range(10):if i+j >5:return i,jprint work()

利用笛卡尔积

这种方法的思路就是,既然可以跳出单循环,我就将多重循环改写为单循环,这可以利用itertools中的笛卡尔积函数product,例如

from itertools import productfor i,j in product(range(10), range(10)):if i+j >5:print i,jbreak

利用调试模式

笛卡尔积的方式很巧妙,也很简洁,但它只能用于每次循环的集合都是独立的情形,假如每层循环都与前一层紧密相关,就不能用这种技巧了。这时候可以用第一种方法,将它写成函数,另外,还可以利用调试模式。这个利用了调试模式中,只要出现报错就退出的原理,它伪装了一个错误出来。

class Found(Exception):passtry:for i in range(10):for j in range(i): #第二重循环跟第一重有关if i + j >5:raise Foundexcept Found:print i, j