以独特而确定的方式将两个整数映射到一个整数
设想两个正整数A和B.我想把这两个整合成一个整数C.
没有其他整数D和E结合到C中，所以把它们和加法运算符结合起来是行不通的。 例如30 + 10 = 40 = 40 + 0 = 39 + 1连接工作也没有。 例如“31”+“2”= 312 =“3”+“12”
这种组合操作也应该是确定性的（总是用相同的input产生相同的结果）， 并且应该总是在整数的正或负上产生一个整数。
你正在寻找一个双射NxN -> N映射。 这些用于例如鸠尾榫 。 看看这个PDF的所谓配对function介绍 。 维基百科引入了特定的配对function，即康托尔配对function ：
三点评论：
- 正如其他人已经明确，如果你打算实现配对function，你可能很快就会发现你需要任意大的整数（bignums）。
- 如果您不想在对（a，b）和（b，a）之间进行区分，请在应用配对function之前对a和b进行sorting。
- 其实我撒谎 你正在寻找一个双射
ZxZ -> N映射。 康托尔的function只适用于非负数。 然而，这不是一个问题，因为很容易定义双射f : Z -> N，如下所示：- 如果n> = 0，则f（n）= n * 2
- 如果n <0，则f（n）= -n * 2 -1
康托尔配对function真的是其中更好的考虑其简单，快速和空间效率之一，但是在这里，在沃尔夫勒姆发表了更好的东西，在这里马修Szudzik 。 Cantor配对函数（相对）的局限性在于，如果input是两个N位整数，则编码结果的范围并不总是保持在2N位整数的范围内。 也就是说，如果我的input是从0 to 2^16 -1两个16位整数，那么可能有2^16 * (2^16 -1)个input组合，所以通过显而易见的鸽巢原理 ，我们需要一个输出大小至less为2^16 * (2^16 -1) ，等于2^32 - 2^16 ，或换句话说， 32位数字的地图应该是理想的可行的。 这在编程世界中可能并不重要。
康托尔配对function ：
(a + b) * (a + b + 1) / 2 + a; where a, b >= 0
对于两个最大的16位整数（65535，65535）的映射将是8589803520，正如你看到的，它不能适合32位。
inputSzudzik的function ：
a >= b ? a * a + a + b : a + b * b; where a, b >= 0
（65535，65535）的映射现在是4294967295，正如你所看到的是一个32位（0到2 ^ 32 -1）的整数。 这就是这个解决scheme的理想之处，它只是利用这个空间中的每一个点，所以没有什么可以获得更多的空间效率。
现在考虑一下我们通常用语言/框架来处理各种大小的数字的签名实现，让我们考虑从-(2^15) to 2^15 -1范围内的有signed 16位整数（稍后我们将看到如何甚至延长输出以跨越签名范围）。 由于a和b必须是正数，因此范围从0 to 2^15 - 1 。
康托尔配对function ：
两个最大的16位有符号整数（32767,32767）的映射将是2147418112，这只是32位有符号整数的最大值。
现在Szudzik的function ：
（32767，32767）=> 1073741823，小得多
我们来考虑负整数。 这超出了我所知道的原始问题，只是为了帮助未来的访问者而详细阐述。
康托尔配对function ：
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。 64位输出的16位input可能是如此不可饶恕！
Szudzik的function ：
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;
（-32768，-32768）=> 4294967295其中32位为无符号范围或64位为有符号范围，但仍然更好。
现在所有这一切，输出一直是积极的。 在签名的世界里， 如果我们可以将一半的输出转移到负轴上 ， 将会节省更多的空间 。 你可以这样做Szudzik的：
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
我所做的事情是：在对input进行权重2并通过函数之后，然后将输出除以2，并将它们中的一部分乘以-1得到负轴。
查看结果，对于有符号16位数范围内的任何input，输出位于有符号的32位整数的极限内，该整数很酷。 我不知道如何去Cantor配对function，但没有尝试尽可能多的效率。 此外，Cantor配对function中涉及的更多计算也意味着其更慢 。
这是一个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整数types（最后2除以2N ）。
我在备用解决scheme上提供的链接很好地描述了利用空间中每个单一点的函数图。 令人惊讶的是，您可以将一对坐标唯一地编码为一个单一的数字！ 魔术世界的数字！
如果A和B可以用2个字节表示，则可以将它们组合成4个字节。 把A放在最重要的一半，把B放在最不重要的一半。
用C语言给出（假设sizeof（short）= 2和sizeof（int）= 4）：
int combine(short A, short B) { return A<<16 | B; } short getA(int C) { return C>>16; } short getB(int C) { return C & 0xFFFF; }
这甚至有可能吗？
你正在结合两个整数。 他们都有范围-2,147,483,648到2,147,483,647，但你只会采取积极的。 这使得2147483647 ^ 2 = 4,61169E + 18个组合。 由于每个组合都必须是唯一的且导致一个整数，所以你需要一些可以包含这个数量的魔法整数。
还是我的逻辑有缺陷？
让a是第一个， b是第二个。 设p是a+1素数， q是b+1素数
然后，结果是pq ，如果a<b,或者2pq如果a>b 。 如果a=b ，让它是p^2 。
正整数的标准math方法是使用素因子分解的唯一性。
f( x, y ) -> 2^x * 3^y
缺点是图像往往会跨越很大的整数范围，所以当用计算机algorithmexpression映射时，可能会遇到select合适的结果types的问题。
你可以修改这个来处理消极的x和y通过编码一个具有5和7项权力的标志。
例如
f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)
f(a, b) = s(a+b) + a ，其中s(n) = n*(n+1)/2
- 这是一个function – 它是确定性的。
- 它也是内射的 – 为不同的（a，b）对映射不同的值。 你可以certificate这一点：
s(a+b+1)-s(a+b) = a+b+1 < a。 - 它返回相当小的值 – 如果您将要使用它来进行数组索引，那么这个值很好，因为数组不必很大。
- 它是caching友好的 – 如果两个（a，b）对彼此靠近，那么f将数字映射到彼此靠近（与其他方法相比）。
我不明白你的意思是：
应该总是在整数的正面或负面上产生一个整数
我如何在这个论坛上写出（大于），（小于）个字符？
对于正整数作为参数和参数顺序无关紧要：
-
这是一个无序的配对function ：
<x, y> = x * y + trunc((|x - y| - 1)^2 / 4) = <y, x> -
对于x≠y，这是一个独特的无序配对函数 ：
<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>
检查这个： http : //en.wikipedia.org/wiki/Pigeonhole_principle 。 如果A，B和C是相同的types，那么就不能完成。 如果A和B是16位整数，而C是32位，那么你可以简单地使用移位。
哈希algorithm的本质是它们不能为每个不同的input提供一个唯一的哈希。
构build映射并不难：
（a，b）！=（b，a）1 2 3 4 5
1 0 1 3 6 10
2 2 4 7 11 16
3 5 8 12 17 23
4 9 13 18 24 31
5 14 19 25 32 40
1 2 3 4 5使用这个映射if（a，b）==（b，a）（mirror）
1 0 1 2 4 6
2 1 3 5 7 10
3 2 5 8 11 14
4 4 8 11 15 19
5 6 10 14 19 24
0 1 -1 2 -2如果你需要负面/正面使用这个
0 0 1 2 4 6
1 1 3 5 7 10
-1 2 5 8 11 14
2 4 8 11 15 19
-2 6 10 14 19 24
弄清楚如何得到一个任意的值，b是有点困难。
虽然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)); }
结果可以适用于整数types的基数的平方根范围内的单个整数。 这比Stephan202更一般的方法略微更有效。 解码也相当简单; 不需要平方根，对于初学者:)
这里是@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 http://stackoverflow.com/a/15391420 x = n y = (x + 1) // 2 while y < x: x = y y = (x + n // x) // 2 return x
你的build议是不可能的。 你将永远有碰撞。
为了将两个对象映射到另一个集合，映射集合必须具有期望组合的最小数量：
假设一个32位的整数，你有2147483647正整数。 select其中的两个顺序无关紧要，重复产生2305843008139952128组合。 这在32位整数的集合中不太合适。
但是，您可以将这个映射放在61位上。 使用64位整数可能是最简单的。 将高位字设置为较小的整数，将低位字设置为较大的一个。
让我们有两个数字B和C，编码成单个数字A
A = B + C * N
哪里
B = A％N = B
C = A / N = C
