我试图在Python [1]中实现以下算法
The problem:(行压缩)设
A是有界度d的n x m数组(即A的每个元素都是整数,a,例如0<a<d.),让k是A的不同行数。找到一个k x m数组,A',这样每一行A都会出现在A'中。
方法:(散列)将A的行哈希到一个表中,跳过重复项并将其余的添加到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年。
发布于 2015-05-29 19:35:28
首先,您需要删除重复的行。为此,您可以使用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)])https://stackoverflow.com/questions/30537601
复制相似问题