笛卡爾乘積（所有的有序對組成的集合）

笛卡爾乘積（所有的有序對組成的集合）

笛卡爾乘積 （所有的有序對組成的集合） 次瀏覽 | 2022.08.25 14:34:59 更新 來源 ：互聯網 精選百科 本文由作者推薦 笛卡爾乘積所有的有序對組成的集合

在數學中，兩個集合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的笛卡爾積表示所有可能的選課情況。A表示所有聲母的集合，B表示所有韻母的集合，那么A和B的笛卡爾積就為所有可能的漢字全拼。

中文名

笛卡爾乘積

外文名

Cartesian product

表達式

A×B={(x,y)|x∈A∧y∈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]

運算性質

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個集合，他們的笛卡爾積所組成的新集合會達到十億個元素。假若某個集合是無限集，那么新的集合就將是有無限個元素。

程序代碼C#源代碼

using System;

using System.Collections;

using System.Collections.Generic;

using System.Text;

using System.Linq;

public class Descartes

{

public static void run(List>dimvalue,List result,int layer, string curstring)

{

if(layer<dimvalue.Count-1)

{

if (dimvalue[layer].Count==0)

run(dimvalue, result, layer+1, curstring);

el

{

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());

}

}

}

el if(layer==dimvalue.Count-1)

{

if(dimvalue[layer].Count==0)result.Add(curstring);

el

{

for(int i = 0; i < dimvalue[layer].Count; i++)

{

result.Add(curstring+dimvalue[layer][i]);

}

}

}

}

}

程序使用說明

（1）將每個維度的集合的元素視為List,多個集合構成List> imvalue作為輸入

（2）將多維笛卡爾乘積的結果放到List result之中作為輸出

（3）int layer, string curstring只是兩個中間過程的參數攜帶變量

（4）程序采用遞歸調用，起始調用示例如下：

List result=new List();

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

即可獲得多維笛卡爾乘積的結果。

參考資料