以唯一且确定的方式将两个整数映射到一个整数

Question

想象一下两个正整数A和B.我想将这两个整数组合成一个整数C.

可能没有其他整数D和E组合为C.因此将它们与加法运算符组合不起作用.例如30 + 10 = 40 = 40 + 0 = 39 + 1连接也不起作用.例如"31"+"2"= 312 ="3"+"12"

这种组合操作也应该是确定性的(总是在相同的输入下产生相同的结果)并且应该总是在整数的正侧或负侧产生整数.

Answer 1

你正在寻找一个双射NxN -> N映射.这些用于例如鸠尾榫.请查看此PDF,了解所谓的配对功能.维基百科介绍了一个特定的配对功能,即Cantor配对功能:

三个评论:

• 正如其他人已经明确指出的那样,如果你计划实现配对功能,你很快就会发现你需要任意大整数(bignums).
• 如果您不想区分对(a,b)和(b,a),则在应用配对功能之前对a和b进行排序.
• 其实我骗了.您正在寻找一个双射ZxZ -> N映射.Cantor的功能仅适用于非负数.但这不是问题,因为很容易定义一个双射f : Z -> N,如下所示:
  • 如果n> = 0,则f(n)= n*2
  • 如果n <0,则f(n)= -n*2 - 1

Answer 2

考虑到它的简单,快速和节省空间,Cantor配对功能确实是最好的之一,但是在这里,Matthew Szudzik在Wolfram上发表了更好的内容.Cantor配对函数(相对)的限制是2N如果输入是两位整数,则编码结果的范围并不总是保持在位整数的范围内N.也就是说,如果我的输入是两位16整数0 to 2^16 -1,那么就有2^16 * (2^16 -1)可能的输入组合,所以通过明显的Pigeonhole原理,我们需要一个至少大小的输出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)整数.这是这个解决方案理想的地方,它只是利用该空间中的每一个点,因此没有什么能够提高空间效率.

现在考虑到我们通常在语言/框架中处理各种大小的数字的签名实现这一事实,让我们考虑signed 16从-(2^15) to 2^15 -1(稍后我们将看到如何将输出扩展到跨越有符号范围的跨度)的位整数.既然a而且b必须是积极的,他们的范围从0 to 2^15 - 1.

康托配对功能:

两个最大16位有符号整数(32767,32767)的映射将是2147418112,它只是有符号32位整数的最大值.

现在Szudzik的功能:

(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;

(-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

我做的事情:在2对输入施加权重并通过函数后,然后我将输出除以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).

我在备用解决方案上提供的链接很好地描绘了利用空间中每个单点的功能图.令人惊讶的是,您可以将一对坐标唯一地编码为一个可逆的数字!神奇的数字世界!!

Answer 3

如果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;
}

Answer 4

这甚至可能吗？
你正在组合两个整数.它们的范围分别为-2,147,483,648到2,147,483,647,但您只能获得正数.这使得2147483647 ^ 2 = 4,61169E + 18种组合.由于每个组合必须是唯一的并且产生一个整数,因此您需要某种可以包含这个数字的神奇整数.

或者我的逻辑是否有缺陷？

Answer 5

让数字a成为第一个,b第二个.我们p是a+1个质数,q是b+1个质数

然后,结果是pq,如果a<b,或2pq如果a>b.如果a=b,就这样吧p^2.

Answer 6

正整数的标准数学方法是使用素数因子分解的唯一性.

f( x, y ) -> 2^x * 3^y

缺点是图像倾向于跨越很大范围的整数,因此当在计算机算法中表达映射时,您可能会遇到为结果选择合适类型的问题.

你可以修改它来处理负数,x并y通过编码功能为5和7项的标志.

例如

f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)

Answer 7

尽管 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 更通用的方法稍微高效一些。解码起来也相当简单；对于初学者来说不需要平方根:)

Answer 8

对于正整数作为参数并且参数顺序无关紧要：

\n\n

\n

1. 这是一个无序配对函数：

   \n\n

   <x, y> = x * y + trunc((|x - y| - 1)^2 / 4) = <y, x>\n

\n

2. 对于 x \xe2\x89\xa0 y，这是一个独特的无序配对函数：

   \n\n

   <x, y> = if x < y:\n           x * (y - 1) + trunc((y - x - 2)^2 / 4)\n         if x > y:\n           (x - 1) * y + trunc((x - y - 2)^2 / 4)\n       = <y, x>\n

\n

\n