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

相关链接

有关组合数学的公式

  1. 排列公式P(n,r)=n!/r!

  2. 组合公式C(n,r)=n!/(r!*(n-r)!)
    C(n,r)=C(n-1,r)+C(n-1,r-1)

  3. 错排公式

    1
    2
    d[1]=0,d[2]=1
    d[n]=(n-1)*(d[n-1]+d[n-2])
  4. 卡特兰数

    • 前几项 : 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()就可以简单的解决
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    /*************************************************************************
    > 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;
    }