排列组合问题

​ 排列组合是组合数学里的两大经典问题，下面我们先来看一下它的定义：

​ 排列：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。

​ 组合：一般地,从n个不同的元素中,任取m(m≤n)个元素为一组,（即不考虑顺序），叫作从n个不同元素中取出m个元素的一个组合。

一、全排列问题

​ 首先我们可以先简化一下这个问题，就令$n=m$n=m，我们可以讨论一下做法。

​ 这个问题很容易看出，我们可以简单粗暴的用dfs暴力求解，当需要排列的数字为n时，时间复杂度明显是$O(2^{n})$O(2n)，效率有点低吧，不过应该不能优化了。其中b数组用于判重。

代码如下（只有P的老师别打我）：

procedure try(x:longint);
var
  i:longint;
begin
  if x>m then
  begin
    print;
    exit;
  end;
  for i:=1 to n do
    if not b[i] then
    begin
      a[x]:=i;
      b[i]:=not b[i];
      try(x+1);
      b[i]:=not b[i];
    end;
end;

​ 在这里安利一波stl库的做法（STL大法好），我们可以用下面这个代码来求解n个元素的全排列问题：

cin >> a;
sort(a,a+n);
int ans=0;
do{
    puts(a);
    ans++;
}while(next_permutation(a,a+n));
cout << ans;

​ 那么这个东西捏，也就是next_permutation这个函数（划重点），它存在于c++的algorithm库中，用途是求a数组的下一个字典序排列，还有个bool类型的返回值，可以直接用于循环的判断。

​ 那么我们现在来看一下全排列问题当$n\leq m$n≤m时，我们又应该怎么办呢？

​ 在我们的dfs程序里只要将输出的判断参数n改成m就行了好白痴啊233。时间复杂度$O(n^{m}) $.

二、全组合问题

​ 明显我们可以看出，这个问题相类似与全排列问题，不过需要判断重复而已。那么其实也很容易想到，我们只需要从前往后搜，不回头就一定不会出现重复的组合并且它一定是按字典序排列的。所以我们可以在我们的dfs中增加一个参数，每次记录下当前搜到的位置，传到下一层就从这个位置的后一位继续搜。

​ 时间复杂度，emmm，好像很难算的样子，应该可以用组合公式求出，就先卖一个关子。

​ 在luogu上还有这样子的玄学做法：将一个数组x的m项赋值为0，其它赋值为1，先从小到大排序，就可以通过上面那一个next_permutation这个函数来求每一个x数组的每一个排列。在每一个排列中，我们可以输出x数组中值为0的项。复杂度$O(n^{m}·m)$O(nm⋅m).

​ 代码。。给一下吧：

for(int i=r+1;i<=n;++i)
        x[i]=1; 
    do{
        for(int i=1;i<=n;++i)
            if(x[i]==0) printf("%3d",i);
        printf("\n");
    }while(next_permutation(x+1,x+n+1));

​ 其实这两个问题的裸题很水的呢。。。。。。

##拓展：

排列以及组合在数学上的公式

​ 其实这个不算拓展，很基础的了，小学奥数学过的都知道。

​ 排列:首先从n个数中取得m个数的排列可以用这个$A_{n}^{m}$Anm​来表示，有时候我们也用P，然后这个东西又有这样子的公式存在：
$A^{m}_{n}=\prod^{n}_{i=n-m+1}i=\frac {n!} {(n-m)!}$Anm​=i=n−m+1∏n​i=(n−m)!n!​
​ 这个东西捏，还比较好证，我已经想到了一种巧妙的证明方法，但这里空白太小，写不下了（逃

​ 组合：这个东西可以用这个$C^{m}_{n}$Cnm​来表示，这玩意儿的公式长成这样：````````````
$C_{n}^{m}=\frac {A_{n}^{m}} {A^{m}_{m}}=\frac {n!} {m!(n-m)!}=\prod^{n}_{i=n-m+1}\div {m!} ,C^{0}_{n}=0$Cnm​=Amm​Anm​​=m!(n−m)!n!​=i=n−m+1∏n​÷m!,Cn0​=0
​ 长得很丑，但是真的很好用啊啊啊。

###Lucas定理

​ 这个东西捏，就是这么一个东西： $C^{n}_{m}\%p=C^{n/p}_{m/p}\times C^{n\%p}_{m\%p}\%p$Cmn​%p=Cm/pn/p​×Cm%pn%p​%p.

​ 这么一长串，本蒟蒻也不清楚怎么证明，想要看证明的话，请出门右拐，不过你可能需要较强的数学基础和数论功底才能看懂这个东西。

​ 贴下代码（引用于这里）

int Lucas (ll n , ll m , int p) 
{
  return m == 0?1:1ll*comb(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}

​ 至于那个comb函数，就是一个普通的组合函数啦，取过膜的，就直接暴力问题不大。

​ 时间复杂度$O(log_{p}n*p)$O(logp​n∗p),这里p指的是模数且为质数。

​ 但在p=2的时候，我们可以用一些玄学算法来搞一搞。因为要判断它的奇偶性，我们可以将它转换成二进制，然后数它1的个数，当且仅当n，m两个数字2的因子个数相同时，这个式子才是奇数，不然就是偶数。二进制能让我们想到什么？位运算啊~所以我们可以用这个式子if n&m==m来判定奇偶性。

牛顿二项式定理

​ 实在不想贴这玩意儿，太长了……就不用markdown了，直接贴上公式：

​ (a+b)^n=C(n,0)an+C(n,1)a^{(n-1)b+…+C(n,i)a}(n-i)b^{i+…+C(n,n)b}n

​ 在中国也叫杨辉三角形，就是一个三角形，自行百度可以看看这玩意儿长什么样，其实就是我们可以发现杨辉三角第n行第m项就是$C^{m-1}_{n-1}$Cn−1m−1​的值，是这样没错了……吧。

​

​ 以上就是本人对排列组合问题的一点见解，如有不对欢迎指正。