作者littleshan (我要加入剑道社!)
看板C_and_CPP
标题Re: [问题] 请教关於一些排列组合的问题
时间Fri Apr 24 11:42:24 2009
※ 引述《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
1F：推 Yshuan:原po好强... 写程式碰到数学真的很苦手阿... 04/24 21:01
2F：推 pran:多谢多谢，我的数学真的是不怎麽行，谢谢高手 04/25 10:27
※ 编辑: littleshan 来自: 59.121.113.147 (04/25 11:34)