python - 如何在 Python 中散列一行？

Question

我正在尝试在 Python 中实现以下算法 [1] :

The problem: (row compression) Let A be an n x m array of bounded degree d (i.e., each element of A is an integer, a, such that 0<a<d.), and let k be the number of distinct rows of A. Find a k x m array, A', such that each row of A appears in A'.

---

The Method: (Hashing) Hash the rows of A into a table, skipping duplicates and adding the rest to A'.

我不明白如何在 Python 中散列一行？

好吧，我想了解“将 A 的行散列到表中”是什么意思。我的理解如下。假设我有一个这样的矩阵:

A = [[1, 2, 3, 4], 
     [1, 2, 3, 4],
     [6, 7, 5, 4]]

因此，我(以某种方式)对它的行进行哈希处理，得到:

B = [x1, x2, x3]

哪里xi是行 i 的散列.在这里我会有 x1=x2因为第 1 行和第 2 行是相等的。自从我得到 x1=x2 ，我会保留一个，我终于拥有了:

A' = [[1, 2, 3, 4], 
      [6, 7, 5, 4]]

我说的对吗？如果是这样，我如何在 Python 中实现这样的算法？

谢谢。

---

[1] D. Comer，“使用尝试删除有界度数组的重复行”，普渡大学，1977 年。

Answer 1

首先，您需要删除重复的行。为此，您可以使用 set，但首先您需要将所有行转换为不可变对象(immutable对象)类型。

您可以将它们转换为元组:

>>> A = [[1, 2, 3, 4], 
...      [1, 2, 3, 4],
...      [6, 7, 5, 4]]
>>> 
>>> map(tuple,A)
[(1, 2, 3, 4), (1, 2, 3, 4), (6, 7, 5, 4)]

然后就可以使用set了。由于 set 使用哈希函数，结果将自动哈希:

>>> set(map(tuple,A))
set([(1, 2, 3, 4), (6, 7, 5, 4)])