排列与组合

一 排列

数学定义

A m n quad A_m^n Amn表示在m个数中取出n个数，并进行全排列，当m=n时，为全排列，可写为 n ! n! n!。 A m n = m ( m − 1 ) ( m − 2 ) . . . . ( m − n ) A_m^n=m(m-1)(m-2)....(m-n) Amn=m(m−1)(m−2)....(m−n)

代码实现（求排列的种类）：

int arrange(int m,int n)
{
          
   
    if(m==n) return n;
    return m*arrange(m-1,n);
}

排列的具体形式

 在这里我们可以用dfs（深度优先搜索）去解决,思路如下：  从第一个数开始，让其等于 1 , 2 , 3 , 4... n 1,2,3,4...n 1,2,3,4...n,以此类推到第n个数，且前面用过的数后面就不能再用，我们用 m a r k [ ] mark[] mark[]去记录这个数，并在每一次执行到n后回溯。  代码如下：

void dfs(int x){
          
   
    if(x==n){
          
   
    for(int i=1;i<=n;i++) 
    printf("%d",a[i]);
    }
    for (int i=1; i<=n; i++) {
          
   
        if(!mark[i]) {
          
   a[x]=i;mark[i]++;
        }
        dfs(x+1);
        mark[i]=0;//回溯
    }
}

输出每一种排序的可能

二 组合

数学意义：

  C m n C_m^n Cmn表示从m个数中取出n个数的方法数，想要求出这个数我们有两种方法：

 法一： C m n = m ( m − 1 ) ( m − 2 ) . . . . ( m − n ) n ! C_m^n= frac{m(m-1)(m-2)....(m-n)}{n! } Cmn=n!m(m−1)(m−2)....(m−n)

 法二： C m n = C m − 1 n + C m − 1 n − 1 C_m^n=C_{m-1}^n+C_{m-1}^{n-1} Cmn=Cm−1n+Cm−1n−1

代码实现

//法一
int cnm(int n,int m){
          
   
    if(n==1) return m;
    return m*cnm(n-1, m-1)/n;
}
//法二
int cnm(int n,int m){
          
   
    if(n==1) return m;
    if(n==m)return 1;
    return (cnm(n,m-1)+cnm(n-1, m-1));
}

求组合的具体形式

咱们依然是用dfs去解决

void dfs(int x)
{
          
   
    if(x==m+1){
          
   for(int j=1;j<=m;j++)                 printf("%d",a[j]);return;
    }
    for (int i=a[x-1]+1; i<=n; i++) {
          
   
        a[x]=i;
        dfs(++x);
        x--;
    }
}