将一个整数范围可逆地映射到另一个整数范围的算法？

Question

什么是时间高效和空间高效的算法，用于将整数的离散范围(比如区间 I1 [A..B]，其中 B>=A)线性映射到另一个更大的整数范围(比如区间I2 [C..D] 其中 D>=C)?

这里为了简单介绍，限制第二区间I2的大小大于或等于第一区间I1，即D-C >= B-A。

因此，I1 中的每个整数映射到 I2 中包含的一组一个或多个对应的整数(因为 I2 的大小大于 I1 的大小)。相反，I2 中的每个整数恰好映射回 I1 中的唯一对应整数。

所以有两种所需的算法，它们在两个提供的整数区间的域中运行:区间 I1 [A..B] 和区间 I2 [C..D](其中 B>=A 且 D>=C 且D-C >= B-A)

1. 算法 A1:给定 I1 中包含的整数 X，计算 I2 中相应的线性映射整数集。将其表示为 A1(I1,I2,X) = [M..N]，其中 [M..N] 是 I2 的子区间。

2. 算法 A2:给定区间 I2 中包含的整数 Y，计算 I1 中的单个对应整数。将其表示为 A2(I1,I2,Y) = X。

算法 A2 必须是 A1 的对称逆。也就是说，对于 I1 中的所有 X:A1(I1,I2,X) = [M..N]，然后对于 [M..N] 中的所有 Y:A2(I1,I2,Y) = X

显然，由于此问题仅限于整数，因此映射可能不是完全线性的。例如，如果 I1 包含三个整数 [1..3]，而 I2 包含四个整数 [4..7]，则 I1 中的两个整数将在 I2 中具有单个映射，而 I1 中的第三个整数将具有I2 中的两个映射。来自 I1 的具有两个映射的特定整数是无关紧要的。重要的是，无论算法 A1 选择哪个整数 (X) 具有两个映射(Y 和 Y+1)，算法 A2 都必须将这两个相同的 Y 值从 I1 映射回原始 X。

算法 A1 和 A2 应尽可能创建从 I1 到 I2 的最线性映射。换句话说，如果区间 I1 的大小为 J，区间 I2 的大小为 K(回想一下 K>=J)，则 I1 的每个整数都具有 TRUNC(K/J) 映射或 TRUNC(K/J)+1 映射进入 I2。

算法应占用恒定空间，因此包含一组可能使用截断整数除法和模算术以及其他基本数学函数的代数方程。换句话说，算法无法为需要空间的映射创建表来存储表中的每个映射，因为整数区间的大小可以达到 2^64。

编辑:例如，假设区间 I1 = [0..2] 和区间 I2 = [0..4]。一种正确的解决方案可能是:

Algorithm A1                    Algorithm A2
X=0, Y=[0..1]                   Y=0, X=0
X=1, Y=[2..3]                   Y=1, X=0
X=2, Y=[4]                      Y=2, X=1
                                Y=3, X=1
                                Y=4, X=2

另一个同样正确的解决方案是:

Algorithm A1                    Algorithm A2
X=0, Y=0                        Y=0, X=0
X=1, Y=[1..2]                   Y=1, X=1
X=2, Y=[3..4]                   Y=2, X=1
                                Y=3, X=2
                                Y=4, X=2

一个不正确的解决方案是:

Algorithm A1                    Algorithm A2
X=0, Y=[0..1]                   Y=0, X=0
X=1, Y=[2..3]                   Y=1, X=1
X=2, Y=[4]                      Y=2, X=1
                                Y=3, X=2
                                Y=4, X=2

上述解决方案不正确。尽管 A1 确实将 [0..2] 线性映射到 [0..4]，并且 A2 确实将 [0..4] 线性映射回 [0..2]，但问题是 A2 不是 A1 的逆.例如，对于 X=0，A1(0) 的其中一个值是 Y=1，但 A2(1) 给出 X=1(而不是原始值 0)。

Answer 1

您可以使用 multiplicative inverse 轻松做到这一点, 和一个偏移量。从减去 A 开始，然后进行乘法逆计算，并通过添加 C 来转换结果。

要反转它，减去 D，进行乘法逆计算的逆运算，然后加上 A。

这很好用。我过去用过它，效果很好。