[問題] 給一個m*n(m<=n)矩陣，每列取一個非零ꐠ…
給一個 3*4 矩陣 M, 如下:
A B C D E
a 1 1 0 1 0
M = b 0 0 1 0 0
c 0 1 0 0 1
其中每一列中，1代表可以對應，0代表不可對應。
例如:第一列 a 可以對應於 A, B, D，不可對應於C, E。
欲求 a,b,c 一一對應(one-to-one)於 A,B,C,D,E 的所有可能。
也就是有如下結果：
a b c, a b c, a b c, a b c, a b c
| | | | | | | | | | | | | | |
A C B, A C E, B C E, D C B, D C E
共五種。
想請問，這種問題適合用遞迴嗎，特別是當矩陣大小達到20*33時？
有沒有類似問題的演算法？
如果要用遞迴的話，我的想法是：
矩陣M中的第一列，有"三個"非零元素，
A B C D E
a 1 1 0 1 0
M = b 0 0 1 0 0
c 0 1 0 0 1
for i = 1 to "3"
if !(M包含某列元素皆為0)
{
1.取第i個非零元素, i=1 時為 M(a,A), 紀錄此mapping (a,A)
2.將第a列,第A行刪除,得:
B C D E
M = b 0 1 0 0
c 1 0 0 1
3. 再用此M去遞迴
其中,當M為空時, 列出mapping結果.
}
不知道這樣的想法OK不OK，
因為其中有個for loop，所以不知道該怎麼把mapping的過程記錄下來。
這個演算法我之後希望能套用到一個較大SIZE的矩陣(20*33)，複雜度很高，
我有嘗試過用queue和stack的方式做，在小矩陣上OK，
換了大矩陣後，跑了一天還沒跑完，
不知道有沒有高手可以提供一點意見，感激不盡。
*第一次PO文，不知道這問題適不適合在這個版上，還請見諒。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.25.32.41
※ 編輯: QWWJDQ 來自: 114.25.32.41 (05/23 20:42)
→
05/23 20:44, , 1F
05/23 20:44, 1F
→
05/23 20:45, , 2F
05/23 20:45, 2F
→
05/23 21:03, , 3F
05/23 21:03, 3F
→
05/23 21:12, , 4F
05/23 21:12, 4F
→
05/23 21:13, , 5F
05/23 21:13, 5F
→
05/23 21:14, , 6F
05/23 21:14, 6F
→
05/23 21:16, , 7F
05/23 21:16, 7F
→
05/24 00:17, , 8F
05/24 00:17, 8F
推
05/24 17:04, , 9F
05/24 17:04, 9F
推
05/24 17:15, , 10F
05/24 17:15, 10F
→
05/24 18:59, , 11F
05/24 18:59, 11F
→
05/24 19:00, , 12F
05/24 19:00, 12F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 4 篇)：