python - 从 N*N*N 到 N 的双射函数

Question

谁能帮我从 N * N * N → N 中找到一个双射数学函数，它接受三个参数 x、y 和 z 并返​​回数字 n？

我想知道函数 f 及其反函数 f'，如果我有 n，我将能够通过应用 f'(n) 来确定 x、y、z。

Answer 1

将 f 定义为更简单函数 g 的组合

假设 g 是从 N × N 到 N 的双射，并令 g^-1 为其倒数。然后我们可以用 g 来定义 f，如下所示。

f(x, y, z) = g(g(x, y), z) = n

f^-1(n) = (x, y, z) 其中 g^-1(n) = (w, z) 且 g^{- 1(w)=(x，y)}

将 g 定义为从 N × N 到 N 的双射

我们现在有一个更简单的问题，即定义 g。

g(x, y) = (x + y)(x + y + 1)/2 + y = n

g^-1(n) = (x, y) 其中 m = ⌊(2n)^1/2⌋ 并且以下两个条件之一成立。

• x + y = m 且 y = n - m(m + 1)/2

• x + y = m - 1 且 y = n - m(m - 1)/2

Python 实现

def f(x, y, z):
    return g(g(x, y), z)

def f_inv(n):
    w, z = g_inv(n)
    x, y = g_inv(w)
    return (x, y, z)

def g(x, y):
    return (x + y) * (x + y + 1) / 2 + y

def g_inv(n):
    m = math.floor(math.sqrt(2 * n))
    while True:
        y = n - m * (m + 1) / 2
        if y >= 0:
            break
        m -= 1
    x = m - y
    return x, y