将线性索引中的下标转化为无穷生成元的乘积

Question

我有N无限的生成器。我已经知道如何获得这些无限生成器的笛卡尔积，因为有几种方法列出了here（“zig zag”，“expanding square”等）。我真的不在乎使用哪种方法作为我真正想要的东西的基础：我想将“索引转换为笛卡尔积”转换为“索引元组转换为原始生成器”而不实际迭代笛卡尔积直到那一点。我很清楚，我实际上无法索引到生成器中。那很好，因为我只需要索引本身。基本上，我想要与here描述的一样的东西，但它适用于无限生成器。你知道吗

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

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

假设我使用了zig-zag算法，因为作者非常友好地在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)

同样，它不必是zig-zag算法的线性索引。任何在无限生成元上产生笛卡尔积的算法都可以作为基础。你知道吗

Answer 1

生成笛卡尔积的各种方法都是相同过程的变体：

1. 将乘积元组划分为可数无限个有限大小的块；

2. 依次在每个块中生成元组。

“zigzag”方法和Cantor函数，例如，通过索引的总和来划分块：

For integer i = 0 to infinity
    generate all tuples with sum(component_indexes) == i

“展开平方法”是：

For integer i = 0 to infinity
    generate all tuples with max(component_indexes) == i

等等。。。你知道吗

要直接查找这些方法的第k个元组，请执行以下操作：

1. 设SMALLER（i）为小于i的块中的元组数。求最大值i，使更小（i）<；=k。这是包含kth元组的块的编号。你知道吗
2. 获取（k-SMALLER（i））th元组（从零开始），其块内编号i。你知道吗

对于N维中的“展开平方”方法，例如，较小（i）=i^N所有分量小于i的元组数，因此i=floor（N次方根（k））。设r=k-i^N，然后找到最大分量等于k的rth元组（例如按词法顺序）。你知道吗

然而，最容易直接索引的产品是位交织。在该方案中，乘积索引的二进制展开中的连续位以循环方式分配给分量索引。在python中，它是这样的：

def getProductTerm(dimensions, index):
    ret=[0]*dimensions
    bit=0
    while index>0:
        ret[dimensions-1-(bit%dimensions)]+=(index&1)<<(bit/dimensions)
        index >>= 1
        bit+=1
    return ret

你可以在这里试试：https://ideone.com/0dTMU3

Answer 2

你在尝试反转pairing function。您给出的“zig-zag”算法是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

你可以查看维基百科的链接来获得完整的推导。你知道吗