如何基于某些等价关系从矩阵列表中删除重复项？

Question

给定一些对称整数矩阵列表，我想在以下等价关系下删除所有重复项：

二KXK矩阵M1，M2是等价的，如果有一些排列s上{1,...,k}使得对所有i和j在{1,...,k}我们有M1_ij = M2_s(i)s(j)，即两个矩阵是“平等”的，如果我可以同时置换的行和列得到一个从其他。

不幸的是，我的幼稚方法（在构建列表时，检查列表中是否已存在新矩阵的任何排列）被证明太慢了。

我可能想到的一些可能更快的替代方法是将所有矩阵放入列表，将它们置换为“规范置换”，然后按照此处的描述删除重复项。但是，我也不知道如何在代码中实现这样的“规范排列”。

要进一步缩小范围：矩阵相对较小（k <= 4），列表将包含5或6位数字的矩阵，并且矩阵的必定dtype必须是某种整数类型（当前intc，但我可以更改）。

最终列表的顺序无关紧要，每个对等类的代表也没有生存。如果需要的话，整个过程可能需要花费几个小时，而不是几天。

有某种合理有效的方法可以实现这一目标吗？我是否再次错过了一些很酷的NumPy或SciPy设施，这对我有帮助吗？

---

根据要求，提供了一些小例子来说明等价关系如何工作：

矩阵{{1,1,1},{1,2,0},{1,0,3}}和{{1,1,1},{1,3,0},{1,0,2}}是等价的，因为置换{1,2,3}->{1,3,2}将一个变换为另一个。

矩阵{{1,1,1},{1,2,0},{1,0,3}}和{{1,1,0},{1,2,1},{0,1,3}}不是等价的，您必须在不对角线排列的情况下更改1的位置。

Answer 1

只需使用您的规范方法即可。搜索矩阵中最大的条目，将其放在右上角。然后根据其条目对第一列和第一行进行排序。

A = np.array([[1,2,3,5],
     [3,6,2,6],
     [3,5,7,2],
     [1,3,6,3]])
a = np.where(A == np.amax(A))
sort_colums = np.argsort(A[a[0]].ravel())[::-1]
sort_rows = np.argsort(A[:,a[1]].ravel())[::-1]
Col_sorted = A[:,sort_colums]
Equiv_class = Col_sorted[sort_rows]
#returns [[7, 5, 3, 2],
          [6, 3, 1, 3],
          [3, 2, 1, 5],
          [2, 6, 3, 6]]

正如评论中所指出的，只有当矩阵的条目仅出现一次时，这才有效。如果这种情况确实发生了几次，但不是那么频繁，那么可以通过生成几个等价类来适应这种方法。