Re: [問題] 請教關於一些排列組合的問題
看板C_and_CPP (C/C++)作者littleshan (我要加入劍道社!)時間16年前 (2009/04/24 11:42)推噓2(2推 0噓 0→)留言2則, 2人參與討論串2/2 (看更多)
※ 引述《pran (小潘)》之銘言：
: 我要算的是
: sum((p[i][0]^2)*p[i][1])
: sum((p[i][0]^2)*p[i][2])
: sum((p[i][1]^2)*p[i][0])
: sum((p[i][1]^2)*p[i][2])
: sum((p[i][2]^2)*p[i][0])
: sum((p[i][2]^2)*p[i][1])
: 分別的值
: 當然如果只有三組的話 就是p3取2 =6 有6種情形
: 就可以用硬幹的
: 但是現在我要推廣到n組數據
: 能夠有方法算嗎?
話說，這個問題可以被轉換成簡單的矩陣乘法。
我們先把上面的式子一般化：
令 R[m][n] = Σ p[i][m]^2 * p[i][n]
所以 R[0][1] = sum((p[i][0]^2)*p[i][1])
R[0][2] = sum((p[i][0]^2)*p[i][2])
...
所以你要求的結果，就是 R[0][1]、R[0][2]、R[1][0]、R[1][2] 等等
R 是一個矩陣，除了對角線的元素外，其它元素都是你想要的答案。
那要怎麼算 R？我們發現 R 當中的元素定義符合矩陣乘法的定義，
若我們另外寫出兩個矩陣：
| p[0][0]^2, p[1][0]^2, p[2][0]^2, ... |
| p[0][1]^2, p[0][2]^2, p[0][3]^2, ... |
A = | . . |
| . . |
| . . |
| p[0][0], p[0][1], p[0][2], ... |
| p[1][0], p[1][1], p[1][2], ... |
B = | . . |
| . . |
| . . |
A[i][j] = p[j][i]^2
B[i][j] = p[i][j]
則 R[m][n] = Σ p[i][m]^2 * p[i][n]
= Σ A[m][i] * B[i][n]
所以 R = A x B
所以，依照上面的規則去填寫 A 和 B 兩個矩陣，然後把兩個矩陣乘起來，
你就得到答案了。
矩陣乘法有許多函式庫可供利用，一般來說會比你自己寫迴圈計算要快一點。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.87.151.40
推
04/24 21:01, , 1F
04/24 21:01, 1F
推
04/25 10:27, , 2F
04/25 10:27, 2F
※ 編輯: littleshan 來自: 59.121.113.147 (04/25 11:34)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
