排列组合（递推矩阵）

201 阅读 0 评论 133 点赞

我是靠谱客的博主诚心马里奥，最近开发中收集的这篇文章主要介绍排列组合（递推矩阵），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

排列与组合有什么区别？

排列与元素的顺序有关，组合与顺序无关。
排列与组合

如何递推出对应的排列组合呢？

①组合
通过上面的组合公式可以得到下面的数据表格

nm	0	1	2	3	4	5	6	…
0	0	0	0	0	0	0	0	…
1	1	0	0	0	0	0	0	…
2	1	2	0	0	0	0	0	…
3	1	3	6	0	0	0	0	…
4	1	4	12	24	0	0	0	…
5	1	5	20	60	120	0	0	…
6	1	6	30	20	360	720	0	…
…	…	…	…	…	…	…	…	…

组合递推式
f[n][m] = f[n][m-1] * ( n - m + 1)

②、排列
通过上面的排列公式可以得到下面的数据表格

nm	0	1	2	3	4	5	6	…
0	1	0	0	0	0	0	0	…
1	1	1	0	0	0	0	0	…
2	1	2	1	0	0	0	0	…
3	1	3	3	1	0	0	0	…
4	1	4	6	4	1	0	0	…
5	1	5	10	10	5	1	0	…
6	1	6	15	20	15	6	1	…
…	…	…	…	…	…	…	…	…

排列递推式
f[n][m] = f[n-1][m-1] + f[n-1][m]

代码实现

①组合

//组合
void A(int n){
   for(int i=0; i<=n; i++)
   	f[i][0] = 1;
   for(int i=1; i<=n; i++)
   for(int j=1; j<i; j++)
   	f[i][j] = f[i][j-1] * ( i - j + 1);
}

②、排列

//排列
void C(int n){
	//初始化
   for(int i=0; i<=n; i++)
   	f[i][0] = f[i][i] = 1;
   	
   //递推
   for(int i=1; i<=n; i++)
   for(int j=1; j<i; j++)
   	f[i][j] = f[i-1][j-1] + f[i-1][j];
}