排列组合

排列(Arrangement/Permutation)

百度百科：
从n个不同元素中取出m(m≤n)个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列。
从n个不同元素中取出m个不同元素，所有不同排列的个数称为排列种数或称排列数，记为或(线性写法)。

• 排列数计算公式
  

排列数旧版使用，新版使用，二者含义相同。

• 套路
  直接使用STL函数next_permutation(first,last)循环遍历。

do{
    // 排列的各种情况
}while(next_permutation(first,last));

• 问题
  求解n以内(0~n-1)的所有数字的全排列。

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

int main(){
    int n=0;
    scanf("%d",&n);
    int arr[n];
    for(int i=0;i<n;++i){
        arr[i] = i;
    }
    do{
        for(int i=0;i<n;++i){
            printf("%d ",arr[i]);
        }
        printf("\n");
    }while(next_permutation(arr,arr+n));
}

---

组合(Combination)

百度百科：
从n个不同的元素中，任取m(m≤n)个元素为一组，叫作从n个不同元素中取出m个元素的一个组合。
从n个元素中不重复地选取m个元素的一个组合。所有这样的组合的总数称为组合数，记作或(线性写法)。

• 组合数计算公式
  
• 组合数恒等公式
  
• 组合递推等公式
  
• 问题
  求解n以内(0~n-1)的所有数字的组合结果(所有子集)。

1. 增量构造法

• 原理
  每次选出一个元素放到集合中。

• 分析
  增量构造法是对组合集合的深度遍历。

  
  

• 参考代码

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

void combination(int n,int *A,int cur){
    for(int i=0;i<cur;++i) printf("%d ",A[i]);
    printf("\n");
    int s = cur?A[cur-1]+1:0;// 确定当前元素最小可能值
    for(int i=s;i<n;++i){
        A[cur]=i;
        combination(n,A,cur+1);
    }
}
int main(){
    int n=0;
    scanf("%d",&n);
    int arr[n];
    combination(n,arr,0);
}

执行分析

迭代是横向思维(红色箭头)，递归是纵向思维(黄色箭头)。

对应访问树结构(准确的讲是DAG)也是迭代访问兄弟节点(红色箭头)，递归访问后代节点(黄色箭头)。

下面是演示n为不同值时函数调用的情况。缩进表示递归，缩进相同的表示迭代。

• n=1

combination([],0)
 combination([0 ],1)

• n=2

combination([],0)
 combination([0 ],1)
  combination([0 1 ],2)
 combination([1 ],1)

• n=3

combination([],0)
 combination([0 ],1)
  combination([0 1 ],2)
   combination([0 1 2 ],3)
  combination([0 2 ],2)
 combination([1 ],1)
  combination([1 2 ],2)
 combination([2 ],1)

• n=4

combination([],0)
 combination([0 ],1)
  combination([0 1 ],2)
   combination([0 1 2 ],3)
    combination([0 1 2 3 ],4)
   combination([0 1 3 ],3)
  combination([0 2 ],2)
   combination([0 2 3 ],3)
  combination([0 3 ],2)
 combination([1 ],1)
  combination([1 2 ],2)
   combination([1 2 3 ],3)
  combination([1 3 ],2)
 combination([2 ],1)
  combination([2 3 ],2)
 combination([3 ],1)

• n=5

combination([],0)
 combination([0 ],1)
  combination([0 1 ],2)
   combination([0 1 2 ],3)
    combination([0 1 2 3 ],4)
     combination([0 1 2 3 4 ],5)
    combination([0 1 2 4 ],4)
   combination([0 1 3 ],3)
    combination([0 1 3 4 ],4)
   combination([0 1 4 ],3)
  combination([0 2 ],2)
   combination([0 2 3 ],3)
    combination([0 2 3 4 ],4)
   combination([0 2 4 ],3)
  combination([0 3 ],2)
   combination([0 3 4 ],3)
  combination([0 4 ],2)
 combination([1 ],1)
  combination([1 2 ],2)
   combination([1 2 3 ],3)
    combination([1 2 3 4 ],4)
   combination([1 2 4 ],3)
  combination([1 3 ],2)
   combination([1 3 4 ],3)
  combination([1 4 ],2)
 combination([2 ],1)
  combination([2 3 ],2)
   combination([2 3 4 ],3)
  combination([2 4 ],2)
 combination([3 ],1)
  combination([3 4 ],2)
 combination([4 ],1)

• 性能
  时间复杂度：
  空间复杂度：

2. 位向量法

• 原理
  构造位向量bits[i]，代替增量构造法中的数组arr[]，B[i]为true表示选取，false表示不选。

• 分析
  位向量法是对组合集合的后序深度遍历。

  
  
• 参考代码

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

void combination(int n,bool *bits,int cur){
    if(cur == n){
        for(int i=0;i<cur;++i) {
            if(bits[i]) printf("%d ",i);
        }
        printf("\n");
        return;
    }
    
    bits[cur] = true;
    combination(n,bits,cur+1);
    bits[cur] = false;
    combination(n,bits,cur+1);
}
int main(){
    int n=0;
    scanf("%d",&n);
    bool bits[n];
    combination(n,bits,0);
}

• 性能
  时间复杂度：
  空间复杂度：

3. 二进制法

• 原理
  使用二进制表示元素的取舍(1表示取，0表示舍)。

• 分析

  
  
• 参考代码

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

void combination(int n){
    int size = pow(2,n); // 也可以这样 1<<n;
    for(int i = 0; i < size; ++i){// 遍历二进制数
        for(int j = 0; j < n; ++j){// 遍历0~n的数组
            if((i>>j)&1 == 1){ // 如果对应二进制数为1,表示选择
                cout << j << " ";
            }
        }
        printf("\n");
    }
}
int main() {
   int n = 0;
   scanf("%d",&n);
   combination(n);
   return 0;
}

• 性能
  时间复杂度：
  空间复杂度：

总结

当n=5时，下面是各种方法的输出结果：

4. 应用

1. 已知大小为n数列arr，求数列的所有组合结果(所有子集)。

2. 已知字符串s，求字符串的所有组合结果(所有子集)。

---

5. 分类计数原理

• 加法原理
  做一件事有种方案，第种方案有种方法，则一共有种方法。
• 乘法原理
  做一件事有个步骤，第个步骤有种方法，则一共有种方法。