以唯一且确定性的方式将两个整数映射为一个 [英] Mapping two integers to one, in a unique and deterministic way

问题描述

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

Imagine two positive integers A and B. I want to combine these two into a single integer C.

不能有其他整数 D 和 E 组合成 C.所以将它们与加法运算符结合起来是行不通的.例如 30 + 10 = 40 = 40 + 0 = 39 + 1串联也不起作用.例如 "31" + "2" = 312 = "3" + "12"

There can be no other integers D and E which combine to C. So combining them with the addition operator doesn't work. Eg 30 + 10 = 40 = 40 + 0 = 39 + 1 Neither does concatination work. Eg "31" + "2" = 312 = "3" + "12"

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

This combination operation should also be deterministic (always yield the same result with the same inputs) and should always yield an integer on either the positive or the negative side of integers.

推荐答案

您正在寻找一个双射 NxN ->N 映射.这些用于例如鸽尾.查看这个PDF，了解所谓的配对功能.维基百科引入了一个特定的配对函数，即康托配对函数:

You're looking for a bijective NxN -> N mapping. These are used for e.g. dovetailing. Have a look at this PDF for an introduction to so-called pairing functions. Wikipedia introduces a specific pairing function, namely the Cantor pairing function:

三点说明:

• 正如其他人所说的那样，如果您计划实现配对功能，您可能很快就会发现您需要任意大的整数(bignums).
• 如果您不想区分 (a, b) 和 (b, a) 对，请在应用配对函数之前对 a 和 b 进行排序.
• 其实我撒谎了.你正在寻找一个双射 ZxZ ->N 映射.Cantor 函数仅适用于非负数.然而，这不是问题，因为定义双射很容易 f : Z ->N，像这样:
  • f(n) = n * 2 如果 n >= 0
  • f(n) = -n * 2 - 1 如果 n <0
  • As others have made clear, if you plan to implement a pairing function, you may soon find you need arbitrarily large integers (bignums).
  • If you don't want to make a distinction between the pairs (a, b) and (b, a), then sort a and b before applying the pairing function.
  • Actually I lied. You are looking for a bijective ZxZ -> N mapping. Cantor's function only works on non-negative numbers. This is not a problem however, because it's easy to define a bijection f : Z -> N, like so:
    • f(n) = n * 2 if n >= 0
    • f(n) = -n * 2 - 1 if n < 0

    这篇关于以唯一且确定性的方式将两个整数映射为一个的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！