排列组合以及相关STL总结

#排列组合以及相关STL总结

有关组合数学的公式

排列公式P(n,r)=n!/r!
组合公式C(n,r)=n!/(r!*(n-r)!)
C(n,r)=C(n-1,r)+C(n-1,r-1)
错排公式
```
d[1]=0,d[2]=1
```

d[n]=(n-1)*(d[n-1]+d[n-2]):hexoPostRenderEscape–>

卡特兰数
- 前几项 : 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,208012…
- 公式C(n)=C(2n,n)/(n+1)

STL中的全排列函数

函数声明 : #include<algorithm>

bool next_permutation( iterator start, iterator end);
next_permutation()函数功能是输出全部比当前排列大的排列。顺序是从小到大
prev_permutation()函数功能是输出全部比当前排列小的排列，顺序是从大到小
复杂度
- 至多 N/2 次交换，其中 N = std::distance(first, last)
- 典型实现在排列的整个序列上，平均每次调用使用约 3 次比较和 1.5 次交换
例题 : hdu-1027
用next_permutation()就可以简单的解决

/*************************************************************************
    > File Name: p.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com 
    > Created Time: 2019年05月10日 星期五 10时23分37秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
int n, m;
int num[1010];
int main(){
    while(cin >> n >> m){
        for(int i = 0; i < n; i++){
            num[i] = i + 1;
        }
        m--;
        while(m--){
            next_permutation(num, num + n);
        }
        for(int i = 0; i < n; i++){
            if(i) printf(" ");
            printf("%d", num[i]);
        }
        cout << endl;
    }
    return 0;
}

相关链接

有关组合数学的公式

STL中的全排列函数