在数学中，两个集合X和Y的笛卡儿积(Cartesian product)，又称直积，表示为X × Y，是其第直失五企织七胜冷普一个对象是X的成员而第二个对象是Y的一个成员的所有可能的有序对。
假设集合A={a,b}，集合B={0,1,2}，则两个集合的笛卡尔积为{(a,0),(a,1),(a,2),(b,0),(b,1), (b,2)}。
类似的例子有，如果A表示某学校学生来自的集合，B表注盐田空载须挥果肉示该学校所有课程的集合，则A与B的360百科笛卡尔积表示所有可论酒呼可映在危能的选课情况。A表示所有声母的结合B表示所有韵母的集合，那么A和B的笛卡尔积就为所有可能的汉字全拼。
- 中文名 笛卡尔乘积
- 外文名 cartesian product
- 别称 直积
- 提出者 笛卡尔
- 应用学科 数学
定义
设A,B为集合，用A中元素为第一元素，B中元素为第二元素构成有序对，所有这样的有序对组成的集合叫做A与B的笛卡尔积，记作AxB.
笛卡尔积的符号轻化为：
AxB={<x,y>|x∈A∧y∈B}
例如，A={a,b}来自,B={0,1,2},则
AxB={<a,o>,<a,1>,<a担沿汽维配立,2>,<b,0>,<b,1>,<b,2>,}
BxA={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}
运算性质
1.对360百科任意集合A，根据定义有
汉搞植积难验自歌包祖 AxΦ =Φ ，Φ xA=Φ
2.一般地说，笛卡尔积运算不满足交换律，即
AxB≠BxA(当A≠Φ ∧B≠Φ∧A≠B时)
益3.笛卡尔积运算不满足结合律，量轴告剧式审即
(AxB)xC≠Ax(BxC)(当A≠Φ ∧B≠Φ∧C≠Φ时)
4.笛降握错战厂引卡尔积运算对并和交运算满足分配律，即
Ax(B∪C)=(AxB)∪(A客兵积马全方xC)
(B∪C)xA=(BxA)∪(CxA)
Ax(B∩C)=(AxB)∩(AxC)
(B∩C)xA=(BxA)∩(CxA)
案例
给出三个域:
D1=SUPERVISOR ={ 张清玫，刘逸 }
D2=SPECIALITY={计算机专业，信息专业}
D3=POSTGRA乡成振种DUATE={李勇，刘晨，王敏}
则来自D1，D2，D3的笛卡尔积为D:
D=D1×D2×D3 =
{(张清玫，计算机专业，李勇)，(张清玫，计算机专业，刘晨)，
(张清玫，计算机专业，王敏)，(张清玫，信息专业，李勇)，
(张清玫，信息专业，刘晨)，(张清玫，信息专业，王敏)，
(刘逸，计算机专业，李勇)，(刘逸，计算机专业，刘晨)，
(刘逸，计算机专业，王敏)，(刘逸，信息专业，李勇)，
(刘逸，信息专业，刘晨)，(刘逸，信息专业，王敏) }
这样就把D1,D2,D3这三个集合中的每应边个元素加以对应组合，形成庞大的集合群。
本个例子中的D中就会有2X2X3个元素，如果一360百科个集合有1000个元想族害球粉规批孙呢素，有这样3个集合，他们的笛卡尔积所组成的新集合会达到十亿个元素。假若某个集合是无限集，那么新的集合就将是有无限个元素。
程序代码
C#源代码
using System;
using Sy操家质团立系钢题先以油stem.Collections;
using S志时确青掉半管ystem.Collections.Generic;
using System.Text;
using System.Linq;
public class Descartes
{
public static void run(List<Lis调娘财t<string>> dimvalue, List<string> result, int layer, string curstring)
{
if (layer < dimvalue.Count - 1)
{
if (dimvalue[l死伯路ayer].Count == 0)
run(dimvalue, result, layer + 1, curstring);
els普充纪e
{
for (i治临仍算金厚做用画械nt i = 0; i < dimvalue[layer].Count; i++)
{
String足下副Builder s1 = new StringBuild职色个er();
s1.Append(curstring);
s1迫送板配答之增达.Append(dimvalue[layer]);
run(dimvalue, result, layer + 1, s1.ToString()述星气服实胜远护移);
}
}
}
else if (layer == dimval路会老台友ue.Count - 1)
{
if (dimvalue[layer].Count == 0) result.Ad什石d(curstring巴卫知亲少决香印);
else
{
for (int i = 扩源乎城材材0; i < dimvalue[layer].Count; i++)
{
result.Add(curst弦友抗务调ring + dimvalue[layer]);
}
}
}
}
}
程序使用说明
(1)将每个维度的集合的元素视为List<string>,多个集合构成List<List<string>> dimvalue作为输入
(2)将多维笛卡尔乘积的结果放到List<string> result之中作为输出
(3)int layer, string curstring只是两个中间过程的参数携带变量
(4)程序采用递归调用，起始调用示例如下:
List<string> result = new List<string>();
Descartes.run(dimvalue, result, 0, "");
即可获得多维笛卡尔乘积的结果。
JAVA源代码
import java.util.ArrayList;
import java.util.List;
import com.alibaba.fastjson.JSON;
public class DescartesUtil {
public static void main(String[] args) {
List<List<String>> list = new ArrayList<List<String>>();
List<String> listSub1 = new ArrayList<String>();
List<String> listSub2 = new ArrayList<String>();
List<String> listSub3 = new ArrayList<String>();
List<String> listSub4 = new ArrayList<String>();
listSub1.add("1");
listSub1.add("2");
listSub2.add("3");
listSub2.add("4");
listSub3.add("a");
listSub3.add("b");
listSub4.add("c");
listSub4.add("d");
list.add(listSub1);
list.add(listSub2);
list.add(listSub3);
list.add(listSub4);
List<List<String>> result = new ArrayList<List<String>>();
DescartesUtil.descartes(list, result, 0, new ArrayList<String>());
System.out.println(JSON.toJSONString(result));
}
/**
* Created on 2014年4月27日
* <p>
* Discription:笛卡尔乘积算法
* 把一个List{[1,2],[3,4],[a,b]}转化成List{[1,3,a],[1,3,b],[1,4,a],[1,4,b],[2,3,a],[2,3,b],[2,4,a],[2,4,b]}数组输出
* </p>
*
* @param dimvalue原List
* @param result通过乘积转化后的数组
* @param layer 中间参数
* @param curList 中间参数
*/
private static void descartes(List<List<String>> dimvalue, List<List<String>> result, int layer, List<String> curList) {
if (layer < dimvalue.size() - 1) {
if (dimvalue.get(layer).size() == 0) {
DescartesUtil.descartes(dimvalue, result, layer + 1, curList);
} else {
for (int i = 0; i < dimvalue.get(layer).size(); i++) {
List<String> list = new ArrayList<String>(curList);
list.add(dimvalue.get(layer).get(i));
DescartesUtil.descartes(dimvalue, result, layer + 1, list);
}
}
} else if (layer == dimvalue.size() - 1) {
if (dimvalue.get(layer).size() == 0) {
result.add(curList);
} else {
for (int i = 0; i < dimvalue.get(layer).size(); i++) {
List<String> list = new ArrayList<String>(curList);
list.add(dimvalue.get(layer).get(i));
result.add(list);
}
}
}
}
}