笛卡尔积又名直积，是所有可能的有序对组成的集合，其中有序对的第一个对象是X的成员，第二个对象是Y的成员。可以表示如下：
X×Y=<x,y>|x∈X∧y∈Y
例如，[[a,b],[1,2,3]]的笛卡尔积为[[a,1],[a,2],[a,3],[b,1],[b,2],[b,3]]
在实际应用中，笛卡尔积常用于在电商中生成商品的sku信息，将所有的属性组合起来。
当空间数量固定时，可以直接使用嵌套的循环来完成，例如上面的二元笛卡尔积：
1
2
3
4
5
6
7
8
| let a = ['a','b']
let b = ['1','2','3']
let result = []
for(let i=0;i<a.length;i++){
for(let j=0;j<b.length;j++){
result.push([a[i],b[j]])
}
}
|
output>>>
1
2
3
4
5
6
| [ [ 'a', '1' ],
[ 'a', '2' ],
[ 'a', '3' ],
[ 'b', '1' ],
[ 'b', '2' ],
[ 'b', '3' ] ]
|
推广到n元笛卡尔积：
X1×X2×...×Xn=(x1,...,xn)|x1∈X1∧...∧xninXn
1
2
3
4
5
6
7
| for(let i=0;i<a.length;i++){
for(let j=0;j<b.length;j++){
for(){
...(n次循环)
}
}
}
|
当n不为固定数值的时候，不能以这种嵌套循环的方式表示。因此考虑使用嵌套
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| import copy
def combination(array):
"""
:type array: List[][]
:rtype: List[str]
"""
result = []
if len(array) is 0: return result
def cartsianProduct(index,rs):
if index is len(array):
result.append(rs)
else:
for item in array[index]:
next_rs = copy.copy(rs)
next_rs.append(item)
cartsianProduct(index+1,next_rs)
cartsianProduct(0,[])
return result
combination([['a','b'],['1','2','3']])
|
output>>>
1
| [['a', '1'], ['a', '2'], ['a', '3'], ['b', '1'], ['b', '2'], ['b', '3']]
|
对于python来说，除了使用遍历之外也可以使用py自带的迭代器itertools:
1
2
3
4
| import itertools
rs = []
for x in itertools.product(['a','b'],[1,2,3]):
rs.append(x)
|
output>>>
1
| [('a', 1), ('a', 2), ('a', 3), ('b', 1), ('b', 2), ('b', 3)]
|