排列组合（递推矩阵）

﹏ヽ暗。殇╰゛Y 2023-02-28 01:52 143阅读 0赞

##### 排列与组合有什么区别？ #####

排列与元素的顺序有关，组合与顺序无关。  
![排列与组合][20200719124211373.png]

--------------------

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

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

<table> 
 <thead> 
  <tr> 
   <th>n\m</th> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>…</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>1</td> 
   <td>2</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>1</td> 
   <td>3</td> 
   <td>6</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>1</td> 
   <td>4</td> 
   <td>12</td> 
   <td>24</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>1</td> 
   <td>5</td> 
   <td>20</td> 
   <td>60</td> 
   <td>120</td> 
   <td>0</td> 
   <td>0</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>1</td> 
   <td>6</td> 
   <td>30</td> 
   <td>20</td> 
   <td>360</td> 
   <td>720</td> 
   <td>0</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
  </tr> 
 </tbody> 
</table>

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

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

<table> 
 <thead> 
  <tr> 
   <th>n\m</th> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>…</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>1</td> 
   <td>2</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>1</td> 
   <td>3</td> 
   <td>3</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>1</td> 
   <td>4</td> 
   <td>6</td> 
   <td>4</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>1</td> 
   <td>5</td> 
   <td>10</td> 
   <td>10</td> 
   <td>5</td> 
   <td>1</td> 
   <td>0</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>1</td> 
   <td>6</td> 
   <td>15</td> 
   <td>20</td> 
   <td>15</td> 
   <td>6</td> 
   <td>1</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
   <td>…</td> 
  </tr> 
 </tbody> 
</table>

**排列递推式**  
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];
    }

--------------------

当要求多组排列组合数时，提前生成排列组合矩阵能够有效避免重复运算，提高程序性能。

[20200719124211373.png]: /images/20230209/0ac8346c4c5c43e7961c1cd3b755e427.png

发表评论取消回复

表情：

评论列表（有 0 条评论，143人围观）

还没有评论，来说两句吧...

相关阅读

相关递推转矩阵快速求幂算法

例：给定数列1，1，1，1，3，5，9，17，···，从第4项开始，每项都是前3项的和。求第20202020项的最后4位数是多少。本问题的思路是将数列的求项问题转化为矩

以你之姓@/ 2023年10月05日 13:38/ 0 赞/ 160 阅读

相关爬楼梯问题（DP、DFS、排列组合、递归）

问题描述假设你现在正在爬楼梯，楼梯有 n 级。每次你只能爬 1级或者 2级，那么你有多少种方法爬到楼梯的顶部？我们规定刚开始在第0层。下面介绍4种方法： 1

╰半橙微兮°/ 2023年06月19日 12:30/ 0 赞/ 29 阅读

相关排列组合（递推矩阵）

排列与组合有什么区别？排列与元素的顺序有关，组合与顺序无关。 ![排列与组合][20200719124211373.png] ------------------

﹏ヽ暗。殇╰゛Y/ 2023年02月28日 01:52/ 0 赞/ 144 阅读

相关排列组合

排列组合问题： 1. 字符串全排列(permutation) 转自：[http://www.cnblogs.com/sujz/archive/2011/06/16/20828

我不是女神ヾ/ 2022年09月17日 06:27/ 0 赞/ 382 阅读

相关递推——数字矩阵

数字矩阵 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description

﹏ヽ暗。殇╰゛Y/ 2022年07月13日 13:21/ 0 赞/ 293 阅读

相关 java递归实现排列、组合算法

项目需要，特此记录 / @ input:输入List @ result :排列或组合输出结果 @ temp: 存储某种排列或组合方式

青旅半醒/ 2022年03月15日 12:35/ 0 赞/ 385 阅读

相关组合数学 (二): 排列组合

排列组合公式排列组合代码输出所有排列错位排列输出所有组合公式排列从

本是古典何须时尚/ 2022年02月21日 14:54/ 0 赞/ 485 阅读

相关字符串的排列与组合【Java 递归实现】

我们在笔试中经常会遇到需要对字符串进行排列或者组合的题目。本篇文章对字符串的排列和组合进行递归版本的实现。如果你有更简单易懂的方法，一定要在评论区留下来~ 1、字符串的组合

清疚/ 2022年02月20日 10:55/ 0 赞/ 403 阅读

相关全排列、排列、排列组合

排列组合问题小总结：排列组合方法 1、for循环层层枚举 2、交换递归全排列 /给出

一时失言乱红尘/ 2021年12月20日 02:15/ 0 赞/ 616 阅读

相关排列组合

1.引言 pku的OJ平台1731题，就是求一个输入字符串的全排列。在STL中有两个和排列相关的算法，next\_permutation和prev\_per

以你之姓@/ 2021年10月16日 00:14/ 0 赞/ 686 阅读