python - 可逆笛卡尔积元素/索引转换功能

Question

我有一个问题，我需要识别在索引位置找到的元素 the Cartesian product of a series of lists也可以是相反的，即从一系列列表中元素的唯一组合中识别索引位置。

我编写了以下代码，可以很好地执行该任务:

import numpy as np

def index_from_combination(meta_list_shape, index_combination ):
    list_product = np.prod(meta_list_shape)
    m_factor = np.cumprod([[l] for e,l in enumerate([1]+meta_list_shape)])[0:len(meta_list_shape)]
    return np.sum((index_combination)*m_factor,axis=None)


def combination_at_index(meta_list_shape, index ):
    il = len(meta_list_shape)-1
    list_product = np.prod(meta_list_shape)
    assert index < list_product
    m_factor = np.cumprod([[l] for e,l in enumerate([1]+meta_list_shape)])[0:len(meta_list_shape)][::-1]
    idxl = []
    for e,m in enumerate(m_factor):
        if m<=index:
            idxl.append((index//m))
            index = (index%m)
        else:
            idxl.append(0)
    return idxl[::-1]

例如

index_from_combination([3,2],[2,1])
>> 5
combination_at_index([3,2],5)
>> [2,1]

其中[3,2]描述一系列两个列表，一个包含3个元素，另一个包含2个元素。组合 [2,1] 表示由第一个列表中的第三个元素(零索引)和第二个列表中的第二个元素(同样为零索引)组成的排列。

...如果有点笨拙(并且，为了节省空间，忽略列表的实际内容，而是使用其他地方使用的索引来从这些列表中获取内容 - 但这在这里并不重要)。

注意重要的是我的功能相互镜像，以便:

F(a)==b   and G(b)==a  

即它们是彼此相反的。

从链接的问题来看，事实证明我可以用一行代码替换第二个函数:

list(itertools.product(['A','B','C'],['P','Q','R'],['X','Y']))[index]

这将返回所提供的索引整数的唯一值组合(尽管我心中有一些关于该列表中有多少在内存中实例化的问号 - 但同样，现在这不一定重要)。

我要问的是，itertools 似乎是在构建时就考虑到了这些类型的问题 - 是否有一个与 itertools.product 函数同样简洁的单行逆函数，给定一个组合，例如['A','Q','Y'] 将返回一个整数，描述该组合在笛卡尔积中的位置，这样，如果将该整数输入到 itertools.product 函数会返回原来的组合吗？

Answer 1

将这些组合想象为二维 X-Y 坐标，并使用下标到线性索引转换，反之亦然。因此，使用 NumPy 的内置函数 np.ravel_multi_index用于获取线性索引和 np.unravel_index下标索引，分别成为您的 index_from_combination 和 combination_at_index。

这是一个简单的翻译，不会生成任何组合，所以应该很容易。

示例运行以使事情更清楚 -

In [861]: np.ravel_multi_index((2,1),(3,2))
Out[861]: 5

In [862]: np.unravel_index(5, (3,2))
Out[862]: (2, 1)

如果您出于某种原因不想依赖 NumPy，则数学足够简单，可以实现 -

def index_from_combination(a, b):
    return b[0]*a[1] + b[1]

def combination_at_index(a, b):
    d = b//a[1]
    r = b - a[1]*d
    return d, r

示例运行 -

In [881]: index_from_combination([3,2],[2,1])
Out[881]: 5

In [882]: combination_at_index([3,2],5)
Out[882]: (2, 1)