将整数数组编码为唯一的整数

Question

我有一定数量的int数组，形式如下：

[a,b,c,d,e]

for example:

[2,2,1,1,2]

其中a和b可以是从0到2的整数，c和d可以是0或1，e可以是从0到2的整数。

因此，有：3 * 3 * 2 * 2 * 3：108种可能的这种形式的数组。

我想为每个数组分配一个唯一的从0到107的整数代码。

我陷入了困境，我考虑将数组中的每个数字相加，但对于两个这样的数组：

[0,0,0,0,1] and [1,0,0,0,0]

将两个数相加，和为1。

有什么建议吗？

谢谢。

- user2505650

---

没有按照你的解释做。如果你有108个数组，并且想要给每个数组一个唯一的数字，为什么不直接将值从0加到127呢？ - Alg_D

我想知道是否有一个已知的函数，可以将这样的数组作为输入并输出唯一的整数。因此，每次我将这个数组作为输入时，都会得到相同的唯一输出。 - user2505650

你能枚举并为每个可能的组合添加整数键吗？ - Zhiya

你说你“有一定数量的int数组”。这些数组在什么数据结构中？ - Stefan Pochmann

Answer 1

你可以使用 np.ravel_multi_index 函数：

>>> np.ravel_multi_index([1, 2, 0, 1, 2], (3, 3, 2, 2, 3))
65

验证：

>>> {np.ravel_multi_index(j, (3, 3, 2, 2, 3)) for j in itertools.product(*map(range, (3,3,2,2,3)))} == set(range(np.prod((3, 3, 2, 2, 3))))
True

换个方向回去：

>>> np.unravel_index(65, dims=(3, 3, 2, 2, 3))
(1, 2, 0, 1, 2)

- Paul Panzer

---

太棒了！ - MaxU - stand with Ukraine

Answer 2

这有点像将不同大小进制的数字转换成标准整数。在十进制中，你可以有五个数字，每个数字从0到9，然后通过 i = a*10000 + b*1000 + c*100 + d*10 + e*1 将它们转换为单个整数。

等效地，对于十进制转换，你可以编写 i = np.dot([a, b, c, d, e], bases)，其中 bases = [10*10*10*10, 10*10*10, 10*10, 10, 1]。

你可以用相同的方法处理你的进制，只是你的位置引入的乘数是[3,3,2,2,3]而不是[10,10,10,10,10]。所以你可以设置 bases = [3*2*2*3, 2*2*3, 2*3, 3, 1]（=[36, 12, 6, 3, 1]），然后使用 i = np.dot([a, b, c, d, e], bases)。请注意，如果a、b、c、d和e落在你指定的范围内，这将始终给出0到107之间的答案。

要将 i 转换回数字列表，你可以使用类似以下的代码：

digits = []
remainder = i
for base in bases:
    digit, remainder = divmod(remainder, base)
    digits.append(digit)

另一方面，为了让您的生活更简单，您可能最好使用Paul Panzer的答案，它基本上做同样的事情。(我以前从未将n位数字视为n维网格中单元格的坐标，但事实证明它们在数学上是等价的。np.ravel是为每个单元格分配序列号的简单方法。)

- Matthias Fripp

---

这是从头开始实现np.ravel_multi_index和np.unravel_index。演示得很清晰，并且巧妙地使用了divmod。+1 - wim

Answer 3

这是与霍纳法则类似的另一种方法，用于多项式：

>>> array = [1, 2, 0, 1, 2]
>>> ranges = (3, 3, 2, 2, 3)
>>> reduce(lambda i, (a, r): i * r + a, zip(array, ranges), 0)
65

展开后得到 ((((0*3+1)*3+2)*2+0)*2+1)*3+2 = 65。

- Stefan Pochmann

Answer 4

这些数据很少，以至于你可以直接枚举它们：

>>> L = [[a,b,c,d,e] for a in range(3) for b in range(3) for c in range(2) for d in range(2) for e in range(3)]
>>> L[0]
[0, 0, 0, 0, 0]
>>> L[107]
[2, 2, 1, 1, 2]

如果您需要反向操作（从数组到整数），请为其创建一个查找字典，以便您获得O(1)而不是O(n)：

>>> lookup = {tuple(x): i for i, x in enumerate(L)}
>>> lookup[1,1,1,1,1]
58

- wim

Answer 5

要计算向量的点积，可以按照以下方式进行编程：

In [210]: a1
Out[210]: array([2, 2, 1, 1, 2])

In [211]: a2
Out[211]: array([1, 0, 1, 1, 0])

In [212]: a1.dot(np.power(10, np.arange(5,0,-1)))
Out[212]: 221120

In [213]: a2.dot(np.power(10, np.arange(5,0,-1)))
Out[213]: 101100

应该生成108个唯一的数字 - 使用它们的索引...

- MaxU - stand with Ukraine

Answer 6

如果数组长度不是非常巨大，你可以先计算出权重，然后使用简单的数学公式来获取ID。 代码将会像这样：

#Test Case
test1 = [2, 2, 1, 1, 2]
test2 = [0, 2, 1, 1, 2]
test3 = [0, 0, 0, 0, 2]

def getUniqueID(target):
    #calculate out the weights first; 
    #When Index=0; Weight[0]=1;
    #When Index>0; Weight[Index] = Weight[Index-1]*(The count of Possible Values for Previous Index);
    weight = [1, 3, 9, 18, 36]
    return target[0]*weight[0] + target[1]*weight[1] + target[2]*weight[2] + target[3]*weight[3] + target[4]*weight[4]

print 'Test Case 1:', getUniqueID(test1)
print 'Test Case 2:', getUniqueID(test2)
print 'Test Case 3:', getUniqueID(test3)

#Output
#Test Case 1: 107
#Test Case 2: 105
#Test Case 3: 72
#[Finished in 0.335s]

- Sphinx

---

谢谢，这些权重数字是从哪里来的？ - user2505650