想象两个正整数A和B。我想将它们组合成一个单独的整数C。
没有其他整数D和E可以组合成C。因此，使用加法运算符进行组合不起作用。例如：30 + 10 = 40 = 40 + 0 = 39 + 1，连接操作也不行，例如：“31”+“2”= 312 = “3”+“12”。
这种组合操作还应该是确定性的（对于相同的输入始终产生相同的结果）并且总是产生整数，无论是正整数还是负整数。
20个回答
272
康托二元组函数是非常好的一种函数之一，因为它简单、快速、空间有效。但是，在Wolfram上有更好的函数，由Matthew Szudzik在这里发表。相对而言，康托二元组函数的局限性是编码结果的范围并不总是在两个N位整数的限制内。也就是说，如果我的输入是两个16位整数，范围从0到2^16-1，那么可能会有2^16 * (2^16 -1)种输入组合，所以根据显然的鸽巢原理，我们需要至少2^16 * (2^16 -1)大小的输出，等于2^32-2^16，或者换句话说，理想情况下应该使用32位数字的映射。在编程世界中，这可能并不重要。
康托二元组函数:
(a + b) * (a + b + 1) / 2 + a; where a, b >= 0
对于两个最大的16位整数（65535、65535）的映射将是8589803520，正如您所看到的，它不能适合32位。
输入Szudzik函数：
a >= b ? a * a + a + b : a + b * b; where a, b >= 0
(65535, 65535)的映射现在将为4294967295，如您所见，它是一个32位（0到2^32-1）的整数。这就是为什么这个方案是理想的，它简单地利用了该空间中的每一个点，因此没有任何东西可以更加空间高效。
现在考虑到我们通常处理带符号实现的各种大小的数字在语言/框架中，让我们考虑范围从-(2^15)到2^15-1的有符号16位整数（稍后我们将看到如何扩展输出以跨越已签名的范围）。由于a和b必须为正数，它们的范围为0到2^15-1。
康托对数函数：
两个最大的16位有符号整数（32767，32767）的映射将为2147418112，这仅略小于有符号32位整数的最大值。
现在是Szudzik's function:
(32767，32767) => 1073741823，要小得多...
让我们考虑负整数。我知道这超出了原始问题的范围，但只是为了帮助未来的访问者而阐述。
康托对数函数：
A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
(A + B) * (A + B + 1) / 2 + A;
(-32768, -32768) => 8589803520，这是Int64类型。对于16位输入的64位输出可能如此不可原谅!!
Szudzik的函数：
A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
A >= B ? A * A + A + B : A + B * B;
A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
C = (A >= B ? A * A + A + B : A + B * B) / 2;
a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
(-32768, 32767) => -2147483648
(32767, -32768) => -2147450880
(0, 0) => 0
(32767, 32767) => 2147418112
(-32768, -32768) => 2147483647
我的工作：在对输入进行加权（2），并经过函数处理后，我将输出除以二，并通过乘以-1 将一些输出移动到负轴上。
观察结果，对于任何在有符号 16 位数范围内的输入，输出都在有符号 32 位整数的限制范围内，这很棒。我不确定如何以同样的方式处理Cantor配对函数，但由于效率不高，我没有尝试太多。此外，Cantor配对函数中涉及更多计算意味着它也更慢。
这是一个C#实现。
public static long PerfectlyHashThem(int a, int b)
{
var A = (ulong)(a >= 0 ? 2 * (long)a : -2 * (long)a - 1);
var B = (ulong)(b >= 0 ? 2 * (long)b : -2 * (long)b - 1);
var C = (long)((A >= B ? A * A + A + B : A + B * B) / 2);
return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}
public static int PerfectlyHashThem(short a, short b)
{
var A = (uint)(a >= 0 ? 2 * a : -2 * a - 1);
var B = (uint)(b >= 0 ? 2 * b : -2 * b - 1);
var C = (int)((A >= B ? A * A + A + B : A + B * B) / 2);
return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}
由于中间计算可能超出2N有符号整数的限制，我使用了4N整数类型（最后除以2可将结果还原为2N）。
我提供的备选解决方案链接很好地描绘了利用空间中每个点的函数图。令人惊奇的是，您可以将一对坐标唯一编码为一个数字并可逆转！数字的神奇世界！
- nawfal
8
5修改后的unhash函数对于有符号整数会是什么样子？ - Arets Paeglis
10这个回答让我感到困惑。如果你想将（0,0）到（65535,65535）之间的坐标映射到一个数字上，那么使用“a<<16 + b”在各个方面都更好（更快、更简单、更易理解和更明显）。如果你想将(-32768,-32768)映射到(327687,327687)，只需先减去32768即可。 - BlueRaja - Danny Pflughoeft
2@BlueRaja-DannyPflughoeft 你是对的。如果范围不受限制或未知，则我的答案是有效的。我会更新它。在限制变得重要之前，我就已经写下了这个答案。修改这个答案已经在我的脑海中很长时间了。我会尽快找时间。 - nawfal
1你的哈希函数PerfectlyHashThem(65535, 65535) = 8,589,803,520 = 33位，超过4个字节。
它不是你提到的4294967295。
顺便说一句，我同意@BlueRaja-DannyPflughoeft的观点，如果我们要将2个32位数字组合成一个64位数字，那么位移更好。 - Hung Doan
1@grumpyrodriguiz 我把 "subtract" 拼错了。 - BlueRaja - Danny Pflughoeft
显示剩余3条评论
260
您正在寻找一种双射的
1. 正如其他人已经明确指出的，如果你计划实现一个配对函数，你可能很快就会发现你需要任意大的整数（大数）。
2. 如果你不想区分对偶（a，b）和（b，a），那么在应用配对函数之前对a和b进行排序。
3. 实际上我撒了谎。你正在寻找一个双射的ZxZ -> N映射。Cantor的函数只适用于非负数。然而这并不是一个问题，因为很容易定义一个双射f：Z -> N，如下所示：
- 如果n >= 0，则f(n) = n * 2。 - 如果n < 0，则f(n) = -n * 2 - 1。
NxN -> N 映射。这些映射用于例如 回中切割。请查看 此 PDF 以了解所谓的配对函数的介绍。维基百科介绍了一种特定的配对函数，即康托尔配对函数。
![pi(k1, k2) = 1/2(k1 + k2)(k1 + k2 + 1) + k2]](https://istack.dev59.com/rO1IF.webp)
1. 正如其他人已经明确指出的，如果你计划实现一个配对函数，你可能很快就会发现你需要任意大的整数（大数）。
2. 如果你不想区分对偶（a，b）和（b，a），那么在应用配对函数之前对a和b进行排序。
3. 实际上我撒了谎。你正在寻找一个双射的ZxZ -> N映射。Cantor的函数只适用于非负数。然而这并不是一个问题，因为很容易定义一个双射f：Z -> N，如下所示：
- 如果n >= 0，则f(n) = n * 2。 - 如果n < 0，则f(n) = -n * 2 - 1。
- Stephan202
6
15+1 我认为这是针对无界整数的正确答案。 - Unknown
4我如何重新获得k1、k2的值？ - MinuMaster
4请参阅由newfal解释的Szudzik函数。 - OliJG
1虽然对于无界整数来说这是正确的，但对于有界整数来说并不是最好的选择。我认为@blue-raja的评论远远是最有意义的。 - Kardasis
1这对于非正整数不起作用。例如：（0，0）-> 0，（-1，0）-> 0。 - tkrishtop
57
如果A和B可以用2个字节表示，你可以将它们合并到4个字节上。将A放在最高的一半，B放在最低的一半。
在C语言中，这将得到以下结果（假设sizeof(short)=2且sizeof(int)=4）：
unsigned int combine(unsigned short A, unsigned short B)
{
return ((unsigned)A<<16) | (unsigned)B;
}
unsigned short getA(unsigned int C)
{
return C>>16;
}
unsigned short getB(unsigned int C)
{
return C & 0xFFFF; // or return (unsigned short)C;
}
unsigned short 或 uint16_t，确保在进行 | 或 + 运算之前进行零扩展。否则，使用负的 B 值时，OR 操作将会将高位设置为全 1，而 ADD 操作将会使高半部分减去 1。
强制转换为 (unsigned)A 可以避免窄类型在默认升级为有符号 int 后发生有符号溢出 UB。对于更宽的类型，也必须避免移位时丢失掉需要保留的位，例如 ((uint64_t)A << 32 | B)，因为默认提升停止于 int。
强制转换为 (unsigned)B 并不是必需的；重要的是它最初是 unsigned short B 类型。左侧的 | 是 unsigned 类型，这意味着它也会转换为 unsigned。
您可以在带符号类型中使用此方法，至少可以从 getA 和 getB 中获得有符号类型，并且可以从 combine 返回有符号 int，但输入需要进行零扩展，因此在 C 中您需要将它们设置为 unsigned short。例如： ((unsigned)(unsigned short)A << 16) | (unsigned short)B
建议使用 uint16_t 和 uint32_t，以定义类型宽度以匹配您使用的移位计数。
- mouviciel
2
4
combine()应该返回(unsigned short)(A<<16) | (unsigned short)(B);，以便能够正确地打包负数。 - Andy3@Andy：
A<<16操作会越界，应该改为 return (unsigned int)(A<<16) | (unsigned short)(B);。 - DanSkeel16
这真的可能吗？
您正在组合两个整数。它们的范围都为-2,147,483,648至2,147,483,647，但您只会选取正数。
这使得2147483647^2 = 4.61169E+18 种组合。
由于每个组合必须是唯一的，并且结果为整数，因此您需要某种可以包含这么多数字的神奇整数。
或者我的逻辑有误吗？
- Boris Callens
6
+1 我也是这么认为的（尽管我计算时说A和B的顺序无关紧要） - lc.
5是的，根据抽屉原理，您的逻辑是正确的。不幸的是，提问者没有说明这个整数是否有界限。 - Unknown
是的，我也有这个想法，但我认为信息本质上是相同的，所以我没有重新计算。 - Boris Callens
我意识到我应该再次拿起我的机会计算（荷兰语的字面翻译）教材。 - Boris Callens
2@Boris：Kansrekening是“概率论”。 - Stephan202
如果您想处理全范围输入，那么您需要两倍于输入的整数类型宽度。输出将与仅串联两个输入位的大小相同。我假设许多用例对于此具有更有限的输入范围。 - Peter Cordes
10
假设数字a是第一个，b是第二个。假设p是第a+1个质数，q是第b+1个质数。
那么，如果a<b，结果就是pq；如果a>b，结果为2pq。如果a=b，结果为p^2。
- ASk
3
4我怀疑你不想要一种 NP 的解决方案。 - user44242
1对于a=5，b=14和a=6，b=15，这不会产生相同的结果吗？ - Lieven Keersmaekers
6两个不同质数的乘积不可能得到相同结果（唯一质因数分解）。
a=5，b=14 -> 结果为1347 = 611
a=6，b=15 -> 结果为1753 = 901。 - ASk
9
对于正整数，标准的数学方法是使用质因数分解的唯一性。
f( x, y ) -> 2^x * 3^y
缺点是图像往往涵盖了相当大的整数范围，因此在编写计算机算法时，您可能会遇到选择适当类型的问题。
您可以通过使用5和7次幂项来编码标志来修改此内容以处理负的x和y。
例如：
f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)
- CB Bailey
3
数学没问题。但是，正如Boris所说，如果你想将其作为计算机程序运行，你必须考虑到机器的有限性。该算法仅适用于相关机器中可表示的整数子集。 - Yuval F
3我在第二段已经说明了这一点。问题的标签包括“算法”、“数学”和“确定性”，并没有特定的语言要求。输入范围可能不受限制，环境可能具有无限制整数类型“bigint”。 - CB Bailey
这个方法可以工作，但比康托对偶函数慢得多，需要指数运算（固定基数）。2^x部分很简单，只需左移，但3^y部分不同。即使使用二进制指数运算，也需要约log2(y)次乘法（乘以3，因此只是一个x86“lea reg，[reg + reg * 2]”），但仍然是带有移位和CMOV或分支的循环。这似乎没有比现有替代方案更优，除非实际数字对某些用例很有趣。在回答中讨论有趣，但仅限于为什么它是次优的。 - Peter Cordes
6
尽管Stephan202的答案是唯一真正通用的，但对于有限范围内的整数，您可以做得更好。例如，如果您的范围是0..10,000，则可以执行以下操作：
#define RANGE_MIN 0
#define RANGE_MAX 10000
unsigned int merge(unsigned int x, unsigned int y)
{
return (x * (RANGE_MAX - RANGE_MIN + 1)) + y;
}
void split(unsigned int v, unsigned int &x, unsigned int &y)
{
x = RANGE_MIN + (v / (RANGE_MAX - RANGE_MIN + 1));
y = RANGE_MIN + (v % (RANGE_MAX - RANGE_MIN + 1));
}
结果可以适合一个整数范围，最多达到整数类型基数的平方根。这比Stephan202的更普遍的方法稍微更有效地打包。它也更容易解码，起步不需要平方根 :)
- bdonlan
2
这对浮点数有可能吗？ - Lukas
@Lukas：一般来说，由于浮点数的舍入误差和精度限制，除非浮点数恰好是相当接近的数字，否则这几乎是不可能的。你想用慢速的
fmod恢复的数字y，会被从一个更大的数字x * range中加上的舍入误差所“污染”。将一个小数加到一个大数上会丢失大部分较小数的精度。想想FP加法的工作原理：将它们的尾数移位以对齐它们（基于指数），然后相加，并截断为尾数宽度（实际上是四舍五入）。因此，你会移出许多y的有效位。 - Peter Cordes5
对于正整数作为参数且参数顺序不重要的情况：
Here's an unordered pairing function:
<x, y> = x * y + trunc((|x - y| - 1)^2 / 4) = <y, x>For x ≠ y, here's a unique unordered pairing function:
<x, y> = if x < y: x * (y - 1) + trunc((y - x - 2)^2 / 4) if x > y: (x - 1) * y + trunc((x - y - 2)^2 / 4) = <y, x>
- ma11hew28
4
f(a, b) = s(a+b) + a，其中s(n) = n*(n+1)/2
- 这是一个函数 - 它是确定性的。
- 它也是单射的 - f将不同的值映射到不同的(a,b)对。你可以使用以下事实证明这一点：
s(a+b+1)-s(a+b) = a+b+1<a。 - 它返回相当小的值 - 如果您要将其用于数组索引，则很好，因为数组不必很大。
- 它对缓存友好 - 如果两个(a,b)对彼此接近，则f将数字映射到彼此接近的数字(与其他方法相比)。
我不明白您的意思：
应该始终在整数的正侧或负侧产生整数
我该如何在这个论坛中写入“大于”、“小于”符号？
- libeako
2
2大于和小于字符应该在
反引号转义 中正常工作。 - TRiG这相当于康托对偶函数，因此不能处理负整数。 - Davor Josipovic
4
这里是@DoctorJ代码的扩展，基于@nawfal给出的方法来处理无界整数。它可以进行编码和解码。它适用于普通数组和numpy数组。
#!/usr/bin/env python
from numbers import Integral
def tuple_to_int(tup):
""":Return: the unique non-negative integer encoding of a tuple of non-negative integers."""
if len(tup) == 0: # normally do if not tup, but doesn't work with np
raise ValueError('Cannot encode empty tuple')
if len(tup) == 1:
x = tup[0]
if not isinstance(x, Integral):
raise ValueError('Can only encode integers')
return x
elif len(tup) == 2:
# print("len=2")
x, y = tuple_to_int(tup[0:1]), tuple_to_int(tup[1:2]) # Just to validate x and y
X = 2 * x if x >= 0 else -2 * x - 1 # map x to positive integers
Y = 2 * y if y >= 0 else -2 * y - 1 # map y to positive integers
Z = (X * X + X + Y) if X >= Y else (X + Y * Y) # encode
# Map evens onto positives
if (x >= 0 and y >= 0):
return Z // 2
elif (x < 0 and y >= 0 and X >= Y):
return Z // 2
elif (x < 0 and y < 0 and X < Y):
return Z // 2
# Map odds onto negative
else:
return (-Z - 1) // 2
else:
return tuple_to_int((tuple_to_int(tup[:2]),) + tuple(tup[2:])) # ***speed up tuple(tup[2:])?***
def int_to_tuple(num, size=2):
""":Return: the unique tuple of length `size` that encodes to `num`."""
if not isinstance(num, Integral):
raise ValueError('Can only encode integers (got {})'.format(num))
if not isinstance(size, Integral) or size < 1:
raise ValueError('Tuple is the wrong size ({})'.format(size))
if size == 1:
return (num,)
elif size == 2:
# Mapping onto positive integers
Z = -2 * num - 1 if num < 0 else 2 * num
# Reversing Pairing
s = isqrt(Z)
if Z - s * s < s:
X, Y = Z - s * s, s
else:
X, Y = s, Z - s * s - s
# Undoing mappint to positive integers
x = (X + 1) // -2 if X % 2 else X // 2 # True if X not divisible by 2
y = (Y + 1) // -2 if Y % 2 else Y // 2 # True if Y not divisible by 2
return x, y
else:
x, y = int_to_tuple(num, 2)
return int_to_tuple(x, size - 1) + (y,)
def isqrt(n):
"""":Return: the largest integer x for which x * x does not exceed n."""
# Newton's method, via https://dev59.com/3WUp5IYBdhLWcg3wRV9D#15391420
x = n
y = (x + 1) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x
- NStarman
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
10,001*A + B吗？ - BlueRaja - Danny Pflughoeft