複雜性：一個矩陣是另一個矩陣

給定兩個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

複雜性：一個矩陣是另一個矩陣

回答

相關問題