配对函数 -- 来自 Wolfram MathWorld

配对函数是一个可逆地将映射到的函数，其中 $Z^*={0,1,2,...}$ 表示非负整数。配对函数自然地出现在证明有理数和非负整数的基数相同，即，其中被称为 aleph-0，最初由 Georg Cantor 提出。配对函数也出现在编码问题中，在这些问题中，整数值的向量需要可逆地折叠成单个整数值。

设

(1)

然后 Hopcroft 和 Ullman（1979，第 169 页）定义了配对函数

			(2)
			(3)

如上表所示，其中。逆函数可以从以下公式计算得出

Hopcroft-Ullman 函数可以重新参数化，使得和在中，而不是中。这个函数被称为康托函数，由下式给出

(8)

如上表所示。它的逆函数由下式给出

Fueter 和 Pólya 的一个定理指出，康托尔配对函数和 Hopcroft 与 Ullman 的变体是唯一具有实值系数的二次函数，可以将可逆地映射到 (Stein 1999, pp. 448-452)。

Stein (1999) 提出了两种回文式（“牛耕式”）变体，如上所示，但没有给出明确的公式。

还有其他定义配对函数的方法。例如，Pigeon（2001，第 115 页）提出了一个基于位交织的配对函数。这个“按位”配对函数，如上所示，定义为

$<i,j>_P={_|_ if i=j=0; <|_i/2_|,|_j/2_|>_(SP):i_0:j_0 otherwise,$

(12)

其中（和）是（或）的最低有效位，是连接运算符，符号是空位字符串

要配对两个以上的数字，可以使用配对的配对。例如，可以定义为或，但应定义为，以最小化由此产生的数字的大小。一般的方案是

等等。

配对函数