Re: [問題] 給一個m*n(m<=n)矩陣，每列取一個非零ꐠ…
如果問題是要找出一組 one-to-one 對應，
可以把問題轉成 Maximum Bipartite Matching，
然後用 Hangerian Algorithms(匈牙利演算法) 去找出一組解。
但是從你的題目敘述上看來，
你並不是只要找出一組解，而是要找出所有解。
根據 Wikipedia: http://en.wikipedia.org/wiki/Sharp-P-complete
"How many perfect matchings are there for a given bipartite graph?"
此問題是個 #P-complete problem，
雖然此處是 perfect matching，和你的問題不完全相同，
但 perfect matching 可以視為你的問題中的一個特例，
連 perfect matching 都是 #P-complete，
可見你的問題至少也是 #P-complete。
這類問題如果只需要計算所有解的 "數量" 且數字不大時， (n<20)
"也許" 還有機會用 DP 算出。複雜度大概 O( 2^n * ... )
至於要算到 20*33，我個人是認為沒有辦法。
當然，如果 bipartie graph 本身非常的稀疏，那就又另當別論了。
順便一提，這種問題其實也可以發在 Prob_solve 板。
※ 引述《QWWJDQ (夢想十足總是失足)》之銘言：
: 給一個 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
: 共五種。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.78.231
※ 編輯: tkcn 來自: 140.114.78.231 (05/23 21:28)
推
05/23 22:10, , 1F
05/23 22:10, 1F
→
05/23 22:16, , 2F
05/23 22:16, 2F
→
05/23 22:17, , 3F
05/23 22:17, 3F
→
05/23 22:24, , 4F
05/23 22:24, 4F
討論串 (同標題文章)