[Math] Cartesian Product (or Descartes Product, Product Set)

Cartesian Product (or Descartes Product)

공집합(empty set, null set)이 아닌 여러 sets를 이용하여 새로운 set을 만드는 연산.

 

Cartesian product는

• operand인 여러 집합들의
• 각 elements를  원소(component, element)로 하는 tuple을 element(원소)로 하는 set을 반환함.

 

2개의 집합 $A$, $B$의 Cartesian product $A\times B$는 다음과 같음.

$$A\times B= \{ (a,b) | a \in A, b\in B\}$$

 

$n$ 개의 집합 $A_1, A_2, \dots, A_n$의 Cartesian Product는 다음과 같이 정의됨.

$$\displaystyle \prod^n_{i=1}A_i=A_1 \times A_2 \times \cdots \times A_n=\{(x_1,x_2,\dots,x_n)|\forall i: x_i \in A_i\}$$

---

참고로, 두 집합 $A$, $B$의 Cartesian Product $A\times B$의 subset $R$은 $A$에서 $B$로의 relation (관계) 가 됨.

Relation에 대한 자세한 내용은 다음을 참고

2024.02.25 - [.../Math] - [Math] Relation

[Math] Relation

---

용어 Cartesian 의 유래

“René Descartes”라는 이름을 라틴어로 쓰면, “Renatus”는 그의 성인 “René”에 해당하고, “Cartesius”는 그의 성인 “Descartes”에 해당함. 라틴어 이름은 주로 academic field에서 사용되는 특성을 보임.

---

Example

$X$가 $x$-축 상에서 같은 간격으로 떨어진 $M$개의 값들로 구성된 set이고, $Y$가 $y$-축 상에서 같은 간격으로 떨어진 $N$개의 값들로 구성된 set인 경우, 이 두 set의 Cartesian product는 $M\times N$ rectangular array의 좌표(coordinate)를 정의함.

---

itertools.product(*iterable, repeat=1)

Python의 itertools 모듈의 product 함수가 이  Catersian Product를 구현하고 있음.

• 단, set 을 argument로 사용하지 않고 sequence에 해당하는 iterable 객체들이 argument로 할당됨.
• "여러 argument들의 item들로 이루어진 그룹들"을 item으로 가지는 iterator를 반환함.

 

다음 예제를 확인할것.

# --------------------------
# 일반적인 cartesian product 수행.
>>> A = [0,1,2]
>>> B = ['a','b']
>>> for i in itertools.product(A,B,repeat=1):
...     print(i)
... 
(0, 'a')
(0, 'b')
(1, 'a')
(1, 'b')
(2, 'a')
(2, 'b')
# --------------------------
# repeat 인자의 사용법을 보여줌.
>>> for i in itertools.product(A,B,repeat=2):
...     print(i)
... 
(0, 'a', 0, 'a')
(0, 'a', 0, 'b')
(0, 'a', 1, 'a')
(0, 'a', 1, 'b')
(0, 'a', 2, 'a')
(0, 'a', 2, 'b')
(0, 'b', 0, 'a')
(0, 'b', 0, 'b')
(0, 'b', 1, 'a')
(0, 'b', 1, 'b')
(0, 'b', 2, 'a')
(0, 'b', 2, 'b')
(1, 'a', 0, 'a')
(1, 'a', 0, 'b')
(1, 'a', 1, 'a')
(1, 'a', 1, 'b')
(1, 'a', 2, 'a')
(1, 'a', 2, 'b')
(1, 'b', 0, 'a')
(1, 'b', 0, 'b')
(1, 'b', 1, 'a')
(1, 'b', 1, 'b')
(1, 'b', 2, 'a')
(1, 'b', 2, 'b')
(2, 'a', 0, 'a')
(2, 'a', 0, 'b')
(2, 'a', 1, 'a')
(2, 'a', 1, 'b')
(2, 'a', 2, 'a')
(2, 'a', 2, 'b')
(2, 'b', 0, 'a')
(2, 'b', 0, 'b')
(2, 'b', 1, 'a')
(2, 'b', 1, 'b')
(2, 'b', 2, 'a')
(2, 'b', 2, 'b')
>>>

---

Example0

NumPy 를 이용한 구현: meshgrid 와 flatten을 활용한 예제임.

import numpy as np

# 두 배열 정의
a = np.array([1, 2, 3])
b = np.array([4, 5])

# numpy.meshgrid를 사용하여 Cartesian product 구하기
A, B = np.meshgrid(a, b)

# 결과를 2차원 배열로 변환
cartesian_product = np.array([A.flatten(), B.flatten()]).T

print(cartesian_product)

---

다음 gist 는 tensorflow와 pytorch에서의 구현하고 있음.

https://gist.github.com/dsaint31x/c9f1f533440a84db5c2033314defee21

dl_cartesian_product.ipynb

https://dsaint31.github.io/math/math-week01/#class-set-and-relation

[Math] Week 01

---