可逆笛卡尔积元素/索引转换功能 [英] Invertable Cartesian Product Elements/Index Translation Function

问题描述

我遇到一个问题，我需要确定在其中的索引位置找到的元素 笛卡尔产品，也可以是相反的，即从一系列列表中元素的唯一组合中识别索引位置.

I have a problem where I need to identify the elements found at an indexed position within the Cartesian product of a series of lists but also, the inverse, i.e. identify the indexed position from a unique combination of elements from a series of lists.

我编写了以下代码，可以很好地完成任务:

I've written the following code which performs the task reasonably well:

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]表示由第一个列表中的第三个元素(零索引)和第二个列表中的第二个元素(零索引)组成的排列.

Where [3,2] describes a series of two lists, one containing 3 elements, and the other containing 2 elements. The combination [2,1] denotes a permutation consisting of the 3rd element (zero-indexing) from the 1st list, and the 2nd element (again zero-indexed) from the second list.

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

...if a little clunkily (and, to save space, one that ignores the actual contents of the lists, and instead works with indexes used elsewhere to fetch the contents from those lists - that's not important here though).

重要的是我的功能相互镜像，使得:

N.B. What is important is that my functions mirror one another such that:

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

即它们彼此相反.

从链接的问题中发现，我可以用单线替换第二个功能:

From the linked question, it turns out I can replace the second function with the one-liner:

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

这将返回所提供的索引整数的值的唯一组合(尽管在我的脑海中有一些关于在内存中实例化该列表的数量的问号-再次重申，这现在不一定很重要).

Which will return the unique combination of values for a supplied index integer (though with some question-mark in my mind about how much of that list is instantiated in memory - but again, that's not necessarily important right now).

我要问的是，itertools似乎是在考虑这些类型的问题的基础上构建的-与itertools.product函数是否存在同样整齐的单行逆向函数，在给定组合的情况下，例如['A','Q','Y']将返回一个整数，描述该组合在笛卡尔乘积中的位置，这样，如果将该整数输入itertools.product函数，它将返回原始组合?

What I'm asking is, itertools appears to have been built with these types of problems in mind - is there an equally neat one-line inverse to the itertools.product function that, given a combination, e.g. ['A','Q','Y'] will return an integer describing that combination's position within the cartesian product, such that this integer, if fed into the itertools.product function will return the original combination?

推荐答案

将这些组合想象为二维X-Y坐标，并使用subscript to linear-index conversion和反之.因此，请使用NumPy的内置 np.ravel_multi_index 获取线性索引和 np.unravel_index 用于下标索引，它们分别成为您的index_from_combination和combination_at_index.

Imagine those combinations as two dimensional X-Y coordinates and use subscript to linear-index conversion and vice-verse. Thus, use NumPy's built-ins np.ravel_multi_index for getting the linear index and np.unravel_index for the subscript indices, which becomes your index_from_combination and combination_at_index respectively.

这是一个简单的翻译，不会产生任何组合，因此应该轻而易举.

It's a simple translation and doesn't generate any combination whatsoever, so should be a breeze.

运行样本以使情况更清楚-

Sample run to make things clearer -

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，那么数学就很容易实现-

The math is simple enough to be implemented if you don't want to NumPy dependency for some reason -

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)

这篇关于可逆笛卡尔积元素/索引转换功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！