复杂度：一个矩阵是另一个矩阵的行/列排列

Question

1. 给定两个 mxn 矩阵 A 和 B，它们的元素属于集合 S。 问题：A 的行和列能否置换为 B？解决这个问题的算法的复杂度是多少？行列式有部分帮助（当 m=n 时）：必要条件是 det(A) = +/- det(B)。

2. 还允许 A 包含与 B 的任何元素匹配的“无关紧要”。

3. 此外，如果 S 是有限的，则允许 A 的元素排列。

这不是作业 - 它与已解决的 17x17 拼图有关。

Answer 1

请参阅以下排列矩阵行和列的示例：

观察起始矩阵和结束矩阵。行或列中的所有元素都被保留，只是它们的顺序发生了变化。此外，行和列之间的相对位置的变化是均匀的

例如。请参阅起始矩阵和结束矩阵中的 1。它的行包含元素 12、3 和 14。它的列也有 5、9 和 2。这在整个转换过程中得以维持。

基于这个事实，我提出这个基本算法来查找给定的矩阵 A，其 A 的行和列是否可以排列为矩阵 B。

 1. For each row in A, sort all elements in the row. Do same for B.
 2. Sort all rows of A (and B) based on its columns. ie. if row1 is {5,7,16,18} and row2 is {2,4,13,15}, then put row2 above row1
 3. Compare resultant matrix A' and B'. 
 4. If both equal, then do (1) and (2) but for columns on ORIGINAL matrix A & B instead of rows.
 5. Now compare resultant matrix A'' and B''