排列组合

2018-11-08 本文已影响20人 jdzhangxin

排列(Arrangement/Permutation)

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

排列数计算公式
$A_n^m=n(n-1)\cdots(n-m+1) = \frac{n!}{(n-m)!}$

排列数旧版使用 $P_n^m$ ，新版使用 $A_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个元素的一个组合。所有这样的组合的总数称为组合数，记作 $C_n^m$ 或 $C(n,m)$ (线性写法)。

组合数计算公式
$C_n^m=\frac{P_n^m}{P_m} = \frac{n!}{m!(n-m)!},C_n^0=1$
组合数恒等公式
$C_n^m=C_n^{n-m}$
组合递推等公式
$C_n^m=C_{n-1}^{m-1}+C_{n-1}^{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为不同值时函数调用的情况。缩进表示递归，缩进相同的表示迭代。

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

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

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)

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)

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)

性能
时间复杂度： $O(2^n)$
空间复杂度： $O(n)$

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);
}

性能
时间复杂度： $O(2^n)$
空间复杂度： $O(n)$

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;
}