Algorithm to reversibly map one range of integers into another range of integers?

Question

What is a time-efficient and space-efficient algorithm for linearly mapping a discrete range of integers (say an interval I1 [A..B] where B>=A), into another larger range of integers (say an interval I2 [C..D] where D>=C)?

To simply presentation here, the size of the second range I2 is constrained to be larger than or equal to the first range I1, in other words, D-C >= B-A.

Therefore, each integer in I1 maps to a set of one or more corresponding integers contained in I2 (because the size of I2 is larger than the size of I1). Conversely, each integer in I2 maps back to exactly ONE unique corresponding integer in I1.

So there are two desired algorithms, which operate in a domain of two provided integer intervals: interval I1 [A..B] and interval I2 [C..D] (where B>=A and D>=C and D-C >= B-A)

1. Algorithm A1: Given an integer X contained in I1, compute the corresponding linearly mapped set of integers in I2. Denote this as A1(I1,I2,X) = [M..N] where [M..N] is a sub-interval of I2.

2. Algorithm A2: Given an integer Y contained in interval I2, compute the single corresponding integer in I1. Denote this as A2(I1,I2,Y) = X.

It is essential that algorithm A2 be the symmetric inverse of A1. That is, for all X in I1: A1(I1,I2,X) = [M..N], then for all Y in [M..N]: A2(I1,I2,Y) = X

Obviously since this problem is constrained to integers, the mapping might not be perfectly linear. For example, if I1 contains three integers [1..3], and I2 contains four integers [4..7], then two of the integers from I1 will have a single mapping in I2, and the third integer in I1 will have two mappings in I2. The particular integer from I1 that has two mappings is irrelevant. What is important, is that whichever integer (X) that algorithm A1 selects to have two mappings (Y and Y+1), then algorithm A2 must map those same two Y values back to the original X from I1.

Algorithms A1 and A2 should create the most linear mapping from I1 to I2 that is possible. In other words, if interval I1 has size J and interval I2 has size K (and recall that K>=J), then each integer of I1 has either TRUNC(K/J) mappings or TRUNC(K/J)+1 mappings into I2.

The algorithms should consume constant space, and therefore consist of a set of algebraic equations that probably use truncated integer division and modular arithmetic, and other basic math functions. In other words, the algorithms cannot create a table for the mapping that requires space to store each mapping in a table, since the sizes of the integer intervals can be up to 2^64.

Edit: As an example, suppose interval I1 = [0..2] and interval I2 = [0..4]. One correct solution might be:

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

Another equally correct solution would be:

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

An INCORRECT solution would be:

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

The above solution is incorrect. Although A1 does map [0..2] linearly into [0..4], and A2 does map [0..4] linearly back to [0..2], the problem is that A2 is not the inverse of A1. For example, for X=0 one of the values for A1(0) is Y=1, but A2(1) gives X=1 (instead of the original value of 0).

Answer 1

Instead of using intervals and truncation, I suggest using modular mapping: just map the elements of i1 onto i2 in numerical order, wrapping as needed. Here is code in Python (with some overly simple and redundant assignments for clarity and commonality), and an example on the ranges [2:5] and [4:13]

Code:

def alg_1(x, interval_1, interval_2):
# Map X, an element of interval 1,
#   to a list of elements in interval 2.

    lo_1 = interval_1[0]
    hi_1 = interval_1[1]
    lo_2 = interval_2[0]
    hi_2 = interval_2[1]
    range_1 = hi_1 - lo_1 + 1
    range_2 = hi_2 - lo_2 + 1
    pos_1 = x - lo_1

    base_val = pos_1 + lo_2
    y = range(base_val, hi_2+1, range_1)


    return y

def alg_2(y, interval_1, interval_2):
# Map Y, an element of interval 2,
#   to its corresponding element in interval1.

    lo_1 = interval_1[0]
    hi_1 = interval_1[1]
    lo_2 = interval_2[0]
    hi_2 = interval_2[1]
    range_1 = hi_1 - lo_1 + 1
    range_2 = hi_2 - lo_2 + 1
    pos_2 = y - lo_2

    x = lo_1 + pos_2 % range_1

    return x


i1 = (2, 5)
i2 = (4, 13)

print "X  Y"

for val in range(i1[0], i1[1]+1):
    print val, alg_1(val, i1, i2)

print ""
print "Y  X"

for val in range(i2[0], i2[1]+1):
    print val, alg_2(val, i1, i2)

Output:

X  Y
2 [4, 8, 12]
3 [5, 9, 13]
4 [6, 10]
5 [7, 11]


Y  X
4 2
5 3
6 4
7 5
8 2
9 3
10 4
11 5
12 2
13 3

QUESTION For the X=>Y mapping, this method returns a list of mapped values. The size of this list is |i2| / |i1|. Is that acceptable? It slows down when this ratio gets up to about 2^25.

If you prefer, you can return an xrange instead of a range; that's the generator for the sequence, rather than the sequence itself.

Answer 2

You can do this easily using a multiplicative inverse, and an offset. Start by subtracting A. Then do the multiplicative inverse calculation, and translate the result by adding C.

To reverse it, subtract D, do the inverse of the multiplicative inverse calculation, and add A.

This works quite well. I've used it in the past to good effect.