如何在Python中对行进行散列？

Question

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

问题 ：（行压缩）令A是有界度d的n x m数组（即A的每个元素都是整数a，使得0<a<d。 ），令k为A的不同行数。找到一个k x m数组A'，以便A的每一行都出现在A'中。

---

[The Method ：（散列）将A的行散列到表中，跳过重复项并将其余部分添加到A'中。

我不明白如何在Python中对行进行哈希处理？

嗯，我想了解“将A的行散列到表中”的含义。我的理解如下。假设我有一个像这样的矩阵：

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

所以，我以某种方式对它的行进行哈希处理，然后得到：

B = [x1, x2, x3]

其中xi是行i的哈希值。因为第1行和第2行相等，所以我将得到x1=x2。自从得到x1=x2之后，我将保留一个，最后得到：

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

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

谢谢。

---

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

Answer 1

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

您可以将它们转换为tuple：

>>> 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)])