小编典典

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

all

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

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

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


阅读 86

收藏
2022-05-06

共1个答案

小编典典

您正在寻找双射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
2022-05-06