如何索引笛卡尔积

Question

假设变量

x

和

theta

可以分别取可能值

[0, 1, 2]

和

[0, 1, 2, 3]

。

比方说，在一种实现中，

x = 1

和

theta = 3

。表示这一点的自然方法是使用元组

(1,3)

。但是，我想用单个索引来标记状态

(1,3)

。执行此操作的“强力”方法是形成所有可能的有序对

(x,theta)

的笛卡尔积并查找它：

import numpy as np
import itertools

N_x = 3
N_theta = 4

np.random.seed(seed = 1)
x = np.random.choice(range(N_x))
theta = np.random.choice(range(N_theta))

def get_box(x, N_x, theta, N_theta):
    states = list(itertools.product(range(N_x),range(N_theta)))
    inds = [i for i in range(len(states)) if states[i]==(x,theta)]
    return inds[0]

print (x, theta)
box = get_box(x, N_x, theta, N_theta)
print box

这给出了

(x, theta) = (1,3)

和

box = 7

，如果我们在

states

列表中查找它就有意义了：

[(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3)]

然而，这种“暴力”方法似乎效率低下，因为应该可以预先确定索引而不需要查找它。有没有通用的方法可以做到这一点？ （实际应用中

N_x

和

N_theta

的状态数可能会有所不同，笛卡尔积中可能会有更多的变量）。

Answer 1

如果您始终按字典顺序存储

states

并且

x

和

theta

的可能值始终是从

0

到某个最大值的完整范围（如您的示例所示），您可以使用公式

index = x * N_theta + theta

其中

(x, theta)

是您的元组之一。

这可以通过以下方式推广到更高维度的元组：如果

N

是表示变量范围的列表或元组（因此

N[0]

是第一个变量的可能值的数量等）并且

p

是一个元组，您可以使用以下代码片段将索引放入所有可能元组的按字典顺序排序的列表中：

index = 0
skip = 1
for dimension in reversed(range(len(N))):
    index += skip * p[dimension]
    skip *= N[dimension]

这可能不是最Pythonic的方法，但它显示了正在发生的事情：你将你的元组视为一个超立方体，你只能沿着一个维度移动，但如果你到达边缘，你的坐标在“下一个维度” “维度增加，你的旅行坐标重置。建议读者画一些图。 ;)

Answer 2

我认为这取决于您拥有的数据。如果它们稀疏，最好的解决方案是字典。并且适用于任何元组的维度。

import itertools
import random

n = 100
m = 100
l1 = [i for i in range(n)]
l2 = [i for i in range(m)]

a = {}
prod = [element for element in itertools.product(l1, l2)]
for i in prod:
    a[i] = random.randint(1, 100)

关于性能的一个非常好的来源是这个讨论。

Answer 3

为了完整起见，我将包含 Julian Kniephoff 解决方案的实现，

get_box3

，以及原始实现的稍微修改版本，

get_box2

：

# 'Brute-force' method
def get_box2(p, N):
    states = list(itertools.product(*[range(n) for n in N]))
    return states.index(p)

# 'Analytic' method
def get_box3(p, N):
    index = 0
    skip = 1
    for dimension in reversed(range(len(N))):
        index += skip * p[dimension]
        skip *= N[dimension]
    return index

p = (1,3,2)         # Tuple characterizing the total state of the system
N = [3,4,3]         # List of the number of possible values for each state variable

print "Brute-force method yields %s" % get_box2(p, N)
print "Analytical method yields %s" % get_box3(p, N)

“暴力”和“分析”方法都会产生相同的结果：

Brute-force method yields 23
Analytical method yields 23

但我希望“分析”方法更快。按照 Julian 的建议，我已将表示形式更改为

p

和

N

。

Answer 4

对于要从中生成产品的任意列表列表，您可以使用索引

0

到

N-1

（其中

N = prod([len(i) for i in lists])

）对可能的产品进行索引。您可以使用演示/答案中使用的惰性生成器从索引生成所需的产品here。如果您想知道给定产品的索引，可以修改该例程以给出它：

import math

class LazyCartesianProduct:
    def __init__(self, sets):
        self.sets = sets
        self.divs = []
        self.mods = []
        self.maxSize = 1
        self.precompute()

    def precompute(self):
        for i in self.sets:
            self.maxSize = self.maxSize * len(i)
        length = len(self.sets)
        factor = 1
        for i in range((length - 1), -1, -1):
            items = len(self.sets[i])
            self.divs.insert(0, factor)
            self.mods.insert(0, items)
            factor = factor * items

    def entryAt(self, n):
        length = len(self.sets)
        if n < 0 or n >= self.maxSize:
            raise IndexError
        combination = []
        for i in range(0, length):
            combination.append(self.sets[i][ int(math.floor(n / self.divs[i])) % self.mods[i]])
        return combination

    def indexOf(self, p):
        n = 1
        x = 0
        for i, l in zip(p[::-1], self.sets[::-1]):
            x += n*l.index(i)
            n *= len(l)
        return x

>>> lists = [[1, 3, 5], [1, 2, 4], [2, 3, 4, 6], [1, 4, 5, 6], [1, 4, 5]]
>>> lzy = LazyCartesianProduct(lists)
>>> lzy.indexOf([1,2,4,4,5])
77
>>> lzy.entryAt(77)
[1, 2, 4, 4, 5]