欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

排列组合问题

程序员文章站 2022-05-21 23:18:13
...

排列组合问题

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

排列:从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。

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

一、全排列问题

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

​ 这个问题很容易看出,我们可以简单粗暴的用dfs暴力求解,当需要排列的数字为n时,时间复杂度明显是O(2n)O(2^{n}),效率有点低吧,不过应该不能优化了。其中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类型的返回值,可以直接用于循环的判断。

​ 那么我们现在来看一下全排列问题当nmn\leq m时,我们又应该怎么办呢?

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

二、全组合问题

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

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

​ 在luogu上还有这样子的玄学做法:将一个数组x的m项赋值为0,其它赋值为1,先从小到大排序,就可以通过上面那一个next_permutation这个函数来求每一个x数组的每一个排列。在每一个排列中,我们可以输出x数组中值为0的项。复杂度O(nmm)O(n^{m}·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个数的排列可以用这个AnmA_{n}^{m}来表示,有时候我们也用P,然后这个东西又有这样子的公式存在:
Anm=i=nm+1ni=n!(nm)! A^{m}_{n}=\prod^{n}_{i=n-m+1}i=\frac {n!} {(n-m)!}
​ 这个东西捏,还比较好证,我已经想到了一种巧妙的证明方法,但这里空白太小,写不下了(逃

组合:这个东西可以用这个CnmC^{m}_{n}来表示,这玩意儿的公式长成这样:````````````
Cnm=AnmAmm=n!m!(nm)!=i=nm+1n÷m!,Cn0=0 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
​ 长得很丑,但是真的很好用啊啊啊。

###Lucas定理

​ 这个东西捏,就是这么一个东西: Cmn%p=Cm/pn/p×Cm%pn%p%pC^{n}_{m}\%p=C^{n/p}_{m/p}\times C^{n\%p}_{m\%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(logpnp)O(log_{p}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)bi+…+C(n,n)bn

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

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