algorithm - 以独特且确定的方式将两个整数映射为一个

Question

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

不能有其他整数 D 和 E 与 C 结合。因此将它们与加法运算符结合是行不通的。例如 30 + 10 = 40 = 40 + 0 = 39 + 1 串联也不起作用。例如“31”+“2”=312=“3”+“12”

这种组合操作也应该是确定性的（总是用相同的输入产生相同的结果）并且应该总是在整数的正侧或负侧产生一个整数。

score 254 · Accepted Answer

考虑到它的简单、快速和节省空间，康托尔配对功能确实是目前最好的功能之一，但是 Matthew Szudzik在 Wolfram 上发表了更好的东西，这里。2NCantor 配对函数的限制（相对）是，如果输入是两位整数，则编码结果的范围并不总是保持在位整数的范围内N。也就是说，如果我的输入是16从范围内的两位整数0 to 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）整数。这是这个解决方案的理想之处，它只是利用了该空间中的每一个点，因此没有什么能比空间效率更高。

现在考虑到我们通常处理语言/框架中各种大小的数字的有符号实现这一事实，让我们考虑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 配对功能采用相同的方式，但没有尝试过，因为它的效率不高。此外，康托尔配对函数涉及的计算越多，也意味着它的速度越慢。

这是一个 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）。

我在替代解决方案中提供的链接很好地描绘了利用空间中每个点的函数图。令人惊奇的是，您可以将一对坐标唯一地可逆地编码为单个数字！数字的魔法世界！！

score 252 · Accepted Answer

您正在寻找双射NxN -> N映射。这些用于例如接合。查看此 PDF以了解所谓的配对功能。维基百科介绍了一个特定的配对函数，即康托尔配对函数：

pi(k1, k2) = 1/2(k1 + k2)(k1 + k2 + 1) + k2

三个备注：

正如其他人已经明确指出的那样，如果您打算实现配对功能，您可能很快就会发现您需要任意大的整数（bignums）。
如果您不想区分对 (a, b) 和 (b, a)，则在应用配对函数之前对 a 和 b 进行排序。
其实我撒谎了。您正在寻找双射ZxZ -> N映射。康托尔函数仅适用于非负数。然而，这不是问题，因为定义双射很容易f : Z -> N，如下所示：
- f(n) = n * 2如果 n >= 0
- f(n) = -n * 2 - 1如果 n < 0

score 55 · Accepted Answer

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

score 16 · Accepted Answer

这甚至可能吗？
您正在组合两个整数。它们的范围都在 -2,147,483,648 到 2,147,483,647 之间，但您只会选择正数。这使得 2147483647^2 = 4,61169E+18 组合。由于每个组合都必须是唯一的并且结果是一个整数，因此您需要某种可以包含这么多数字的神奇整数。

还是我的逻辑有问题？

score 10 · Accepted Answer

让数字a成为第一个，b第二个。令p为a+1-th 素数，q为b+1-th 素数

然后，结果是pq，如果a<b,或2pq如果a>b。如果a=b，顺其自然p^2。

score 9 · Accepted Answer

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

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

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

您可以修改它以处理负数x，并y通过对具有 5 和 7 项幂的标志进行编码。

例如

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

score 5 · Accepted Answer

尽管 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 的更通用方法更有效地打包。解码也相当简单；对于初学者来说，不需要平方根:)

score 4 · Accepted Answer

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 将数字映射到彼此靠近的它们（与其他方法相比）。

我不明白你的意思：

应该总是在整数的正侧或负侧产生一个整数

我如何在这个论坛上写（大于），（小于）字符？

score 3 · Accepted Answer

检查这个：http ://en.wikipedia.org/wiki/Pigeonhole_principle 。如果 A、B 和 C 是同一类型，则无法完成。如果 A 和 B 是 16 位整数，而 C 是 32 位，那么您可以简单地使用移位。

散列算法的本质是它们不能为每个不同的输入提供唯一的散列。

score 3 · Accepted Answer

构建映射并不难：

   1 2 3 4 5 使用此映射 if (a,b) != (b,a)
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

弄清楚如何获得任意 a,b 的值有点困难。

score 3 · Accepted Answer

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

这是一个无序配对函数：

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

score 3 · Accepted Answer

这是基于@nawfal 给出的方法将@DoctorJ 的代码扩展到无界整数。它可以编码和解码。它适用于普通数组和 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

score 3 · Accepted Answer

更简单的事情怎么样：给定两个数字，A 和 B 让 str 成为连接：'A' + ';' +'B'。然后让输出为 hash(str)。我知道这不是一个数学答案，但是一个简单的 python（它有一个内置的哈希函数）脚本应该可以完成这项工作。

score 2 · Accepted Answer

让我们有两个数字 B 和 C ，将它们编码为单个数字 A

A = B + C * N

在哪里

B=A % N = B

C=A / N = C

score 1 · Accepted Answer

你的建议是不可能的。你总会有碰撞。

为了将两个对象映射到另一个单独的集合，映射的集合必须具有预期组合数的最小大小：

假设一个 32 位整数，你有 2147483647 个正整数。选择其中两个顺序无关紧要且重复产生 2305843008139952128 组合。这不太适合 32 位整数集。

但是，您可以将此映射设置为 61 位。使用 64 位整数可能是最简单的。将高字设置为较小的整数，将低字设置为较大的整数。

score 1 · Accepted Answer

假设你有一个 32 位整数，为什么不把 A 移到前 16 位的一半，把 B 移到另一个？

def vec_pack(vec):
    return vec[0] + vec[1] * 65536;


def vec_unpack(number):
    return [number % 65536, number // 65536];

除了尽可能节省空间且计算成本低之外，一个非常酷的副作用是您可以对压缩数进行矢量数学运算。

a = vec_pack([2,4])
b = vec_pack([1,2])

print(vec_unpack(a+b)) # [3, 6] Vector addition
print(vec_unpack(a-b)) # [1, 2] Vector subtraction
print(vec_unpack(a*2)) # [4, 8] Scalar multiplication

score 0 · Accepted Answer

给定正整数 A 和 B，令 D = A 的位数，E = B 的位数结果可以是 D、0、E、0、A 和 B 的串联。

示例：A = 300, B = 12. D = 3, E=2 结果 = 302030012。这利用了唯一以 0 开头的数字是 0 的事实，

优点：易于编码，易于解码，人类可读，可以首先比较有效数字，无需计算即可进行比较，简单的错误检查。

缺点：结果的大小是一个问题。但这没关系，我们为什么要在计算机中存储无限整数。

score 0 · Accepted Answer

如果您想要更多控制，例如为第一个数字分配 X 位，为第二个数字分配 Y 位，您可以使用以下代码：

class NumsCombiner
{

    int num_a_bits_size;
    int num_b_bits_size;

    int BitsExtract(int number, int k, int p)
    {
        return (((1 << k) - 1) & (number >> (p - 1)));
    }

public:
    NumsCombiner(int num_a_bits_size, int num_b_bits_size)
    {
        this->num_a_bits_size = num_a_bits_size;
        this->num_b_bits_size = num_b_bits_size;
    }

    int StoreAB(int num_a, int num_b)
    {
        return (num_b << num_a_bits_size) | num_a;
    }

    int GetNumA(int bnum)
    {
        return BitsExtract(bnum, num_a_bits_size, 1);
    }

    int GetNumB(int bnum)
    {
        return BitsExtract(bnum, num_b_bits_size, num_a_bits_size + 1);
    }
};

我总共使用 32 位。这里的想法是，例如，如果您希望第一个数字最多为 10 位，第二个数字最多为 12 位，您可以这样做：

NumsCombiner nums_mapper(10/*bits for first number*/, 12/*bits for second number*/);

现在您可以存储num_a最大数量2^10 - 1 = 1023和的num_b最大值2^12 - 1 = 4095。

设置 num A 和 num B 的值：

int bnum = nums_mapper.StoreAB(10/*value for a*/, 12 /*value from b*/);

现在bnum是所有位（总共 32 位。您可以修改代码以使用 64 位）要获得 num a：

int a = nums_mapper.GetNumA(bnum);

要获得数字 b：

int b = nums_mapper.GetNumB(bnum);

编辑： bnum可以存储在类内。我没有这样做，因为我自己的需要我分享了代码并希望它会有所帮助。

感谢来源： https ://www.geeksforgeeks.org/extract-k-bits-given-position-number/ 用于提取位的功能，也感谢mouviciel在这篇文章中回答。使用这些资源我可以找出更高级的解决方案

score 0 · Accepted Answer

我们可以在 O(1) 空间和 O(N) 时间内将两个数字编码为一个。假设您要将 0-9 范围内的数字编码为 1，例如。5和6.怎么做？简单的，

  5*10 + 6 = 56. 
   
    5 can be obtained by doing 56/10 
    6 can be obtained by doing 56%10.

即使对于两位整数，比如说 56 和 45，56*100 + 45 = 5645。我们可以通过执行 5645/100 和 5645%100 再次获得单个数字

但是对于大小为 n 的数组，例如。a = {4,0,2,1,3}，假设我们要编码 3 和 4，所以：

 3 * 5 + 4 = 19               OR         3 + 5 * 4 = 23
 3 :- 19 / 5 = 3                         3 :- 23 % 5 = 3
 4 :- 19 % 5 = 4                         4 :- 23 / 5 = 4

概括后，我们得到

    x * n + y     OR       x + n * y

但我们也需要照顾我们改变的价值；所以它最终成为

    (x%n)*n + y  OR x + n*(y%n)

您可以通过除法并找到结果数字的 mod 来单独获得每个数字。

algorithm - 以独特且确定的方式将两个整数映射为一个

19 回答 19

Related

Reference