笛卡尔乘积是指在数学中，两个集合X和Y的笛卡尓积（Cartesian product），又称直积，表示为X × Y，第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员 [1] 。
定义
笛卡尔乘积是指在数学中，两个
集合
X和
Y的笛卡尓积（Cartesian product），又称
直积，表示为
X×
Y，第一个对象是
X的成员而第二个对象是
Y的所有可能
有序对的其中一个成员
[3]
。
集合
X和
Y的笛卡尓积（Cartesian product），又称
直积，表示为
X×
Y，第一个对象是
X的成员而第二个对象是
Y的所有可能
有序对的其中一个成员
[3]
。
假设集合A={a, b}，集合B={0, 1, 2}，则两个集合的笛卡尔积为{(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}。
类似的例子有，如果A表示某学校学生的集合，B表示该学校所有课程的集合，则A与B的笛卡尔积表示所有可能的选课情况。A表示所有声母的集合，B表示所有韵母的集合，那么A和B的笛卡尔积就为所有可能的汉字全拼。
设A,B为集合，用A中元素为第一元素，B中元素为第二元素构成有序对，所有这样的有序对组成的集合叫做A与B的笛卡尔积，记作AxB.
笛卡尔积的符号化为：
A×B={(x,y)|x∈A∧y∈B}
例如，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)}
运算
1.对任意集合A，根据定义有
AxΦ =Φ , Φ xA=Φ
2.一般地说，笛卡尔积运算不满足交换律，即
AxB≠BxA（当A≠Φ ∧B≠Φ∧A≠B时）
3.笛卡尔积运算不满足结合律，即
(AxB)xC≠Ax(BxC)（当A≠Φ ∧B≠Φ∧C≠Φ时)
4.笛卡尔积运算对并和
交运算满足
分配律，即
交运算满足
分配律，即
Ax(B∪C)=(AxB)∪(AxC)
(B∪C)xA=(BxA)∪(CxA)
Ax(B∩C)=(AxB)∩(AxC)
(B∩C)xA=(BxA)∩(CxA)
案例
给出三个域：
D1=SUPERVISOR = { 张清玫，刘逸 }
D2=SPECIALITY= {计算机专业，信息专业}
D3=POSTGRADUATE = {
李勇，
刘晨，
王敏}
李勇，
刘晨，
王敏}
则D1，D2，D3的笛卡尔积为D：
D=D1×D2×D3 ={(张清玫, 计算机专业, 李勇), (张清玫, 计算机专业, 刘晨),
(张清玫, 计算机专业, 王敏), (张清玫, 信息专业, 李勇),
(张清玫, 信息专业, 刘晨), (张清玫, 信息专业, 王敏),
(刘逸, 计算机专业, 李勇), (刘逸, 计算机专业, 刘晨),
(刘逸, 计算机专业, 王敏), (刘逸, 信息专业, 李勇),
(刘逸, 信息专业, 刘晨), (刘逸, 信息专业, 王敏)}
这样就把D1,D2,D3这三个集合中的每个元素加以对应组合，形成庞大的集合群。
代码
C#源代码
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 32 33 34 35 36 37 | using System; using System.Collections; using System.Collections.Generic; using System.Text; using System.Linq; public class Descartes { public static void run(List<List<string>> dimvalue, List<string> result, int layer, string curstring) { if (layer < dimvalue.Count - 1) { if (dimvalue[layer].Count == 0) run(dimvalue, result, layer + 1, curstring); else { for (int i = 0; i < dimvalue[layer].Count; i++) { StringBuilder s1 = new StringBuilder(); s1.Append(curstring); s1.Append(dimvalue[layer][i]); run(dimvalue, result, layer + 1, s1.ToString()); } } } else if (layer == dimvalue.Count - 1) { if (dimvalue[layer].Count == 0) result.Add(curstring); else { for (int i = 0; i < dimvalue[layer].Count; i++) { result.Add(curstring + dimvalue[layer][i]); } } } } } |
使用说明
（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源代码
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
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>>();
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);
}
}
}
}
}
|
python源代码
|
1
2
3
|
from itertools import product
for x,y,z in product(['a','b','c'],['d','e','f'],['m','n']):
print(x,y,z)
|
今天的文章笛卡尔乘积_计算机中的笛卡尔积分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/69824.html
