Cartesian Product in Python

Posted on Edited on In Views: Word count in article: 673 Reading time ≈ 2 mins.
笛卡尔乘积（Cartesian product），又称笛卡尔积、直积，是一个在计算机领域很常用的集合操作。

定义

笛卡尔乘积（Cartesian product）定义，两个集合$X$和$Y$的笛卡尔积$X\times Y$为第一个对象是$X$的成员而第二个对象是$Y$的成员的所有有序对所组成的集合，如：

$$
\begin{align*}
A\space=&\space\space\left\{a,b\right\}\\
B\space=&\space\space\left\{0,1\right\}\\
A\times B\space=&\left\{(a,0),(a,1),(b,0),(b,1)\right\}
\end{align*}
$$

笛卡尔积也可以扩展为$n$个集合。

实例

Python中有很多能产生笛卡尔积的库函数，它们在与有序对相关的运算中很有用，如GNN中的邻接矩阵等，一些常见的有：

product

1
2
from itertools import product
product(*iterables, repeat=1)

product接受$n$个可迭代对象，并生成它们的笛卡尔积，生成的笛卡尔积也是个可迭代对象，其每个元素是一个元组，代表一个有序对，可以用list将其转化为列表，如：

1
2
3
4
>>> a = [1, 2, 3]
>>> b = ['a', 'b']
>>> print(list(product(a, b)))
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b'), (3, 'a'), (3, 'b')]

repeat代表将前面的可迭代对象重复的次数。如，product(a, b, a, b)等价于product(a, b, repeat=2)：

1
2
3
4
5
6
>>> a = [1]
>>> b = ['a']
>>> print(list(product(a, b, a, b)))
[(1, 'a', 1, 'a')]
>>> print(list(product(a, b, repeat=2)))
[(1, 'a', 1, 'a')]

np.ix_

1
2
import numpy as np
np.ix_(*args)

*args是两个及以上的一维数组，这些数组的数据类型要么是整型int，要么是布尔型bool。np.ix_会返回一个元组，元组的每个元素是一个$n$维的矩阵（取决于输入数组的个数，如果输入两个数组，那么就是$2$维的矩阵），这些元素通过广播机制（broadcasting）生成笛卡尔积。因为这个元组实际上没什么用，所以np.ix_总是被用来进行切片操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
>>> a = [1, 5, 7, 2]
>>> b = [0, 3, 1, 2]
>>> print(np.ix_(a, b))
(array([[1],
       [5],
       [7],
       [2]]), array([[0, 3, 1, 2]]))
>>> x=np.arange(32).reshape((8,4))
>>> print(x)
[[ 0  1  2  3]
 [ 4  5  6  7]
 [ 8  9 10 11]
 [12 13 14 15]
 [16 17 18 19]
 [20 21 22 23]
 [24 25 26 27]
 [28 29 30 31]]
>>> print (x[np.ix_([1,5,7,2],[0,3,1,2])])
[[ 4  7  5  6]
 [20 23 21 22]
 [28 31 29 30]
 [ 8 11  9 10]]

其中，最后的x[np.ix_([1,5,7,2],[0,3,1,2])]使得x被切片出对应下标的元素，如[1, 0]切出4，[1, 3]切出7，最后的[2, 2]切出10。当输入np.ix_的数组的元素类型为bool时，这些数组会被先转化为其True元素的下标所形成的数组，即先进行一次np.nonzero(boolean_sequence)，所以下面这两种切片是等价的：

1
2
3
4
5
6
>>> print(x[np.ix_([False, True, True],[True, True, True, True])])
[[ 4  5  6  7]
 [ 8  9 10 11]]
>>> print(x[np.ix_([1, 2],[0, 1, 2, 3])])
[[ 4  5  6  7]
 [ 8  9 10 11]]