How to hash a row in Python?

Question

I am trying to implement the following algorithm in 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'.

I do not understand how to hash a row in Python?

Well, I would like to understand what does it mean by "hash the rows of A into a table". What I understand is the following. Suppose I have a matrix like this:

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

So, I hash its rows (somehow) and I get:

B = [x1, x2, x3]

where xi is the hash of row i. Here I will have x1=x2 since the row 1 and the row 2 are equal. Since I get x1=x2, I will keep one and I finally have:

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

Am I right? If so, how can I implement such an algorithm in Python?

Thanks.

---

[1] D. Comer, "Removing Duplicate Rows of a Bounded Degree Array Using Tries", Purdue University, 1977 .

Answer 1

First of all, you need to remove the duplicated rows. For that aim, you can use set but first you need to convert all your rows to immutable object types.

You can convert them to 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)]

Then you can use set. And as set uses hash function, the result will be hashed automatically :

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