排列组合

Star_LIcsAy · 2021-10-01 19:22:46 · 个人记录

1.加法原理与乘法原理

• 加法原理：

  其定义指，在完成某件事时，共有 n 类方法。每类方法都有 m_i 种实现，则最后完成该事件的总方法数应为 \sum\limits_{i=1}^n m_i .

  该原理的使用特点为：每类方法都处于同一优先级，每类方法互相之间不干扰。

  （+图）

• 乘法原理

  其定义指，在完成某件事时，共有n个步骤。每个步骤都有 m_i 种实现，每种实现的效果一致，则最后完成该事件的总方法数应为\prod\limits_{i=1}^n m_i(即求 m_i 的积).

  该原理特点为：分步骤完成，每一步之间互相关联，缺一不可。

  （+图）

• （没有例题）；

2.排列

• 从 n 个数中取 m 个，求其总共可能的排列数（即需要考虑不同数字之间的顺序，即使选择同一批数字，若顺序不同，也算是不同的答案）。

• 公式为：A^m_n=n!÷m!

例：P1706 全排列问题

• 全排列问题一般通过 DFS 来实现，当然 C++ 也有自带的全排列函数；

//深搜过程
void dfs(int index){
    if(index>n){
        for(int i=1;i<=m;i++)
            printf("%5d",ans[i]);
        printf("\n");
        return ;
    }
    for(int i=1;i<=n;i++)
        if(!use[i]){
            ans[index]=i;
            use[i]=true;
            dfs(index+1);
            use[i]=false;//恢复现场
            ans[index]=0;
        }
    return ;
}

• 全排列函数的写法：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    int a[25];
    scanf("%d",&n);
   int m=1;
   for(int i=2;i<=n;i++)
        m*=i;
    for(int i=0;i<n;i++)
        a[i]=i+1;
    while(m--){
        next_permutation(a,a+n);//全排列函数
      for(int i=0;i<n;i++)
            printf("%5d",a[i]);
   }
    return 0;
}

3.组合

• 从 n 个数中取 m 个，求其总共可能的组合数（即不需要考虑不同数字之间的顺序，只要选择的数字一样，都算作一种）。

• 公式为：C^m_n=n!÷m!÷(n-m)!

  也就是排列的公式再除以同一种数字组合下可能出现的排列情况。

  特殊性质：若 a+b=n，则 C^a_n=C^b_n.

例：P1157 组合的输出

• 组合数当然也可以用 DFS 来实现，不过为了保证不出现重复的组合以及按照字典序排列，我们令这个队列成为一个单调递增的序列，即每一个数都要大于前一个数，这样就可以保证搜索的时候不重不漏。

• 至于全排列函数……大概不会有人用吧？

//深搜过程
void dfs(int index){
    if(index>m){
        for(int i=1;i<=m;i++)
            printf("%3d",ans[i]);
        printf("\n");
        return ;
    }
    for(int i=ans[index-1]+1;i<=n;i++)
        if(!use[i]){
            ans[index]=i;
            use[i]=true;
            dfs(index+1);
            use[i]=false;
            ans[index]=0;
        }
    return ;
}