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 .

Are you looking for a dict?

Padraic Cunningham
– Padraic Cunningham

2015-05-29 20:02:02 +00:00
Commented May 29, 2015 at 20:02 — Padraic Cunningham
– Padraic Cunningham, Commented May 29, 2015 at 20:02
I think. Is it a hash table?

Kira
– Kira

2015-05-29 21:11:13 +00:00
Commented May 29, 2015 at 21:11 — Kira
– Kira, Commented May 29, 2015 at 21:11
yes it is what you would use for a trie in python

Padraic Cunningham
– Padraic Cunningham

2015-05-29 22:18:46 +00:00
Commented May 29, 2015 at 22:18 — Padraic Cunningham
– Padraic Cunningham, Commented May 29, 2015 at 22:18

kmario23 · Accepted Answer · 2015-05-29 20:24:21Z

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

edited May 29, 2015 at 20:24

kmario23

62.1k17 gold badges174 silver badges159 bronze badges

answered May 29, 2015 at 19:35

Kasravnd

108k19 gold badges167 silver badges195 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to hash a row in Python?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related