笛卡尔乘积是指在数学中，两个集合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 {
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
,多个集合构成List > dimvalue作为输入
,多个集合构成List
（2）将多维笛卡尔乘积的结果放到List
result之中作为输出
result之中作为输出
（3）int layer, string curstring只是两个中间过程的参数携带变量
（4）程序采用递归调用，起始调用示例如下：
List
result = new List
();
result = new List
();
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 new ArrayList Listnew ArrayList Listnew ArrayList Listnew ArrayList Listnew ArrayList 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 new ArrayList descartes(list, result, 0, new ArrayList // System.out.println(JSON.toJSONString(result)); } / * Created on 2014年4月27日 *
* 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]}数组输出
*
* * @param dimvalue原List * @param result通过乘积转化后的数组 * @param layer * 中间参数 * @param curList * 中间参数 */ private static void descartes(List List int layer, List 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++) { Listnew ArrayList 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++) { Listnew ArrayList 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://javaforall.net/198582.html原文链接：https://javaforall.net
