python - 从线性索引获取下标到无限生成器的乘积

Question

我有 N 个无限生成器。我已经知道如何计算这些无限生成器的笛卡尔积，因为列出了几种方法 here (“锯齿形”、“扩展方形”等)。我真的不在乎使用哪种方法作为我真正想要的基础:我想将“索引转换为笛卡尔积”转换为“索引元组转换为原始生成器”实际上迭代笛卡尔积直到那个点。我很清楚我实际上无法索引生成器。这很好，因为我需要的只是索引本身。基本上，我想要描述相同的东西 here但适用于无限发电机。

如果我们考虑一个具体的例子，这将是最容易理解的。让我们只考虑两个生成器 (N=2) 并让它们都是 itertools.count() 这样生成器的索引和生成器的值都是一样。

from itertools import count
a = count()  # 0, 1, 2, ...
b = count()  # 0, 1, 2, ...

假设我使用之字形算法，因为作者非常友好地在 PyPI 上提供了它。

from infinite import product
p = product(a, b)  # (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ...

我想要一个函数，给定 p 的索引，返回 a 和 b 的索引元组，如下所示:

f(2)  # (1,0)
f(4)  # (1,1)

同样，它不必是之字形算法的线性索引。任何在无限生成器上产生笛卡尔积的算法都可以作为基础。

Answer 1

您正在尝试反转 pairing function .您作为示例给出的“之字形”算法是 Cantor pairing function (取决于参数顺序的变化)，由 f(x, y) = (x+y)(x+y+1)/2 + y 给出，它具有如下逆函数。

如果 f^-1(z) = (x, y)，则

w = floor((sqrt(8z+1)-1)/2)
t = w(w+1)/2
y = z-t
x = w-y

您可以查看维基百科链接以获得完整的推导。