Cantor Pairing Function . 칸토어 페어링 함수 . 2개 수로 고유 수 만들기

 

Cantor Pairing Function . 칸토어 페어링 함수 

자연수 ( 0이상의 정수 )  2개 (a, b) 짝과 1:1 대응하는 유일한 정수 만드는 함수. 

서로 다른 페어 는 반드서 서로 다른 숫자가 계산 됨. 

숫자를 역변환 하여 a, b 값 복원 가능. 

 

 

George Cantor .

1870 ~ 1890년대 

집합론(Set Theory) 연구 중  “자연수의 쌍을 자연수 하나로 표현할 수 있는가?”라는 질문에서 등장

 

 

계산 예. 

(1,2) 입력 . 출력 = 8

(2,1) 입력 . 출력 = 7

 

 

 

 

 

C++ 코드 예 

#include <cstdint>
#include <cmath>

/*
수치 안정성 관련 
uint64_t 기준 a, b 가능한 값.
a,b ≤2^16 : 계산값 uint64_t 오버프로우 없이 절대 안전하게 사용 가능. 

주의점
sqrt는 double 사용 → floor 필수

*/

inline uint64_t CantorPair(uint64_t a, uint64_t b)
{
    return ((a + b) * (a + b + 1)) / 2 + b;
}

inline void CantorUnpair(uint64_t z, uint64_t& a, uint64_t& b)
{
    uint64_t w = static_cast<uint64_t>(
        std::floor((std::sqrt(8.0 * z + 1.0) - 1.0) / 2.0)
    );

    uint64_t t = (w * (w + 1)) / 2;
    b = z - t;
    a = w - b;
}

/// 참고 위 w 구하는 실수연산부 대신 정수로 아래처럼 연산 하는 것도 가능하나 속도느림. 
//uint64_t w = 0;
//while ((w+1)*(w+2)/2 <= z) ++w;




//////////////////// 사용예 /////////////////

uint64_t ventity1 = 300;  
uint64_t ventity2 = 1;    

uint64_t symbolID = CantorPair(ventity1, ventity2);

uint64_t ventity1, ventity2;
CantorUnpair(symbolID, ventity1, ventity2);

// ventity1 == 300
// ventity2 == 1

 

 

 

 

 

---

첫 등록 : 2026.01.21

최종 수정 : 

단축 주소 : https://igotit.tistory.com/6418

---