复杂性：一个矩阵是另一个矩阵

给定两个m×n个矩阵A和B的元素属于一组S. 问题的行/列置换：罐的被置换，得到B中的行和列？解决这个问题的算法有多复杂？决定因素部分帮助（当m = n时）：必要条件是det（A）= +/- det（B）。复杂性：一个矩阵是另一个矩阵
还允许含有“无关”匹配B的任何元件
另外，如果S是有限允许A的元素的排列

这是而不是家庭作业 - 这与解决17x17难题有关。

来源

2012-02-20 Lew

这是功课？ – 2012-02-20 16:48:42

参见例如置换矩阵的行和列的下面：

enter image description here

观察开始矩阵和结束矩阵。行或列中的所有元素都会保留，只是它们的顺序发生了变化。相对位置的变化在行和列上是均匀的

例如，在起始矩阵和结束矩阵中见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''

来源

2012-02-20 19:52:27

您无法单独对行进行排序，否则{{1,2}，{3,4}}将等同于{{1,2}，{4,3}}。 – Lew 2012-02-23 01:37:53

如果您使用数组来表示矩阵，那么就可以很容易地进行排序。我同意排序行{{1,2}，{3,4}}之后将等同于{{1,2}，{4,3}}，但它们的差异会在比较排序列后被捕获。你可以干运行逻辑并检查。 – 2012-02-23 04:11:42

请注意，在点＃4中，列上的排序在原始矩阵A和B上完成。排序后的行不会在此后进行处理。 – 2012-02-23 04:15:06

复杂性：一个矩阵是另一个矩阵

回答

相关问题