笛卡尔乘积

背景

笛卡尔1596年3月31日生于法国土伦省莱耳市的一个贵族之家，笛卡尔的父亲是布列塔尼地方议会的议员，同时也是地方法院的法官，笛卡尔在豪华的生活中无忧无虑地度过了童年。

笛卡尔1612年到普瓦捷大学攻读法学，四年后获博士学位。1616年笛卡尔结束学业后，便背离家庭的职业传统，开始探索人生之路。他投笔从戎，想借机游历欧洲，开阔眼界。

在荷兰长达20多年的时间里，笛卡尔对哲学、数学、天文学、物理学、化学和生理学等领域进行了深入的研究，并通过数学家梅森神父与欧洲主要学者保持密切联系。他的主要著作几乎都是在荷兰完成的。思想史中的笛卡尔被视为从近代思想的源头，或者伟大的“父亲”。在哲学领域，他被黑格尔奉为“近代哲学之父”，在经院哲学已然僵死的年代，他以革命者般的激情开辟出近代哲学的辉煌大道；在数学领域，他被冠以“解析几何之父”的尊号，将原本独立的几何和代数关联为公式化的几何坐标体系；在物理学领域，他是牛顿口中的“巨人”之一，基于理性论、机械论缔造了新的自然哲学体系。5

1628年，笛卡尔写出《指导哲理之原则》，1634年完成了以哥白尼学说为基础的《论世界》。书中总结了他在哲学、数学和许多自然科学问题上的一些看法。1637年，笛卡尔用法文写成三篇论文《折光学》、《气象学》和《几何学》，并为此写了一篇序言《科学中正确运用理性和追求真理的方法论》，哲学史上简称为《方法论》，6月8日在莱顿匿名出版。1641年出版了《形而上学的沉思》，1644年又出版了《哲学原理》等重要著作。

1649年冬，笛卡尔应瑞典女王克里斯蒂安的邀请，来到了斯德哥尔摩，任宫廷哲学家，为瑞典女王授课。由于他身体孱弱，不能适应那里的气候，1650年初便患肺炎抱病不起，同年二月病逝。终年54岁。1799年法国大革命后，笛卡尔的骨灰被送到了法国历史博物馆。

定义

笛卡尔乘积是指在数学中，两个集合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这三个集合中的每个元素加以对应组合，形成庞大的集合群。

本个例子中的D中就会有2X2X3个元素，如果一个集合有1000个元素，有这样3个集合，他们的笛卡尔积所组成的新集合会达到十亿个元素。假若某个集合是无限集，那么新的集合就将是有无限个元素。

笛卡尔乘积是从小规模的指定网格构造大规模网络的简单而又重要的构造方法，它能保留小规模网络的许多性质。4

代码

C#源代码

<pre data-lang="c#">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,多个集合构成List> dimvalue作为输入

（2）将多维笛卡尔乘积的结果放到List result之中作为输出

（3）int layer, string curstring只是两个中间过程的参数携带变量

（4）程序采用递归调用，起始调用示例如下：

List result = new List();

Descartes.run(dimvalue, result, 0, "");

即可获得多维笛卡尔乘积的结果。

JAVA源代码

<pre data-lang="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>>();        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源代码

<pre data-lang="python">from itertools import productfor x,y,z in product(['a','b','c'],['d','e','f'],['m','n']):    print(x,y,z)