母函数与排列组合

在谈论母函数问题之前，我们先看一个简单的问题描述：假如有两组数据（A,B）和（C,D），每组中选出一个构成一个组合，总共有几种选法？很显然总共有4种选法：AC,AD,BC,BD。而且很容易联想到这个式子（A+B）*（C+D）=A*C+A*D+B*C+B*D。式子中的几个乘积项就是上面的4种选法。假如把问题换一下：每组中选出一个或0个数据构成组合，总共有几种组合？那么结果就变成：{空},A,B,C,D,AC,AD,BC,BD，而式子（1+A+B）*（1+C+D）=1+C+D+A+A*C+A*D+B+B*C+B*D，正好和上面组合的结果又一致（1代表什么都没选）。从这2个例子我们可以发现多项式乘积和组合存在着某种关系。事实上我们可以这么理解：（1+A+B）可以理解为从第一组数据中取0个数据，取A或者取B，同样（1+C+D）可以理解为从第二组数据取0个数据，取C或者取D。两者相乘的结果就表示了所有的组合。再看一下这个多项式：

　　（1+x）*（1+x+x2）*（1+x3）=1+2x+2x2+2x3+2x4+2x5+x6

　　这个多项式和上面的有一些区别了，它的幂级数超过1了。如果要从（1+x）、（1+x+x2）和（1+x3）中得到x的2次方的话，有两种选择：从（1+x）和（1+x+x2）中分别选择一个x或者从（1+x+x2）中选择x2；如果要得到x的6次方的话，只有1种选择，就是从（1+x）中选择x、（1+x+x2）中选择x2、（1+x3）中选择x3。也就是说乘积结果的每一项anxn的前面的系数an表示了从（1+x）、（1+x+x2）和（1+x3）中得到xn的组合数。

　　其实上面的例子就利用了母函数的思想，下面来具体讨论一下母函数。

一.什么是母函数

　　下面这个对于母函数的描述摘自维基百科：

　　在数学中，某个序列 的母函数是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。

　　也就是说母函数是针对某个序列的，它的外在表现形式是一种形式幂级数。比如说有这样一个序列a0，a1，......an，构造一个函数

　　f(x)=a0+a1x+a2x2+......+anxn

　　则f(x)是序列a0，a1，......an的母函数。比如说最常见的(1+x)n，它是序列C(n,0)，C(n,1)，C(n,2)...C(n,n)的母函数。

　　母函数包括几种，其中最常见的是普通型母函数和指数型母函数。普通型母函数是形如　f(x)=a0+a1x+a2x2+......+anxn的函数，而指数型母函数是形如G(x) = a0 + a1*(x)/1! + a2*(x2)/ 2! + a3*(x3)/3! + …… an*(xn)/k!的函数。

二.利用普通型母函数解决组合问题

　利用母函数的思想可以解决很多组合问题，下面举例说明：

　1.口袋中有白球2个，红球3个，黄球1个，从袋中摸出3个球有几种取法？

　   和上面描述的例子类似，我们可以用次数代表球的个数，多项式的每一项前面的系数代表取法的种树。

　　可以很容易地写出下面这个式子：

　　（1+x+x2）（1+x+x2+x3）（1+x）

 　　（1+x+x2）表示有白球2个，1表示白球不取，x代表取1个白球，x2代表取2个白球，即用x的次数表示取球的个数，后面的也是类似。那么这个多项式的乘积就把所有的情况都表示出来了，对于最终乘积的每一项anxn，表示取n个球有an种取法。

    2.有若干个1克，2克，5克的砝码，要称出20克的重量，有多少种称法？

　　这里不限制砝码的个数，无所谓，照样写出母函数：

　　（1+x+x2+x3+......xk+....）（1+x2+x4+x6......+x2n+......）（1+x5+x10+......x5m+......）

　　因为要称出20克，所以只需要找找到结果中次数为20 的那一项就可以得到结果。

    3.同样对于正数划分也可以解决，比如有整数20，划分成1，2，5，有多少种划分方法？

　　解法和2的类似。

     还有一类题目和这类似，有n个球放到m个盒子中，有多少种不同的放法？

    （1+x+x2+x3+...xk+...）（1+x+x2+x3+...xk+...）（1+x+x2+x3+...xk+...）总共有m项，然后找出乘积中次数为n的那一项系数。

三.利用指数型母函数解决排列问题

　　1.口袋中有白球2个，红球3个，黄球1个，任取3个作为一个排列，总共有多少种排列？

　　类似地用指数型母函数解决

　　用（1+x/1!+x2/2!）表示取白球0个，1个或者2个

　　那么（1+x/1!+x2/2!）（1+x/1!+x2/2!+x3/3!）（1+x/1!）来表示所有的排列结果。

 　 =1+3x+4x2+19x3/6+19x4/12+6x5/12+x6/12

　  =1+3*(x/1!)+8*(x2/2!)+19*(x3/3!)+38*(x4/4!)+60*(x5/5!)+60*(x6/6!)

　　找到次数为3的那一项，系数为19，那么总共有19种排列。

　　2.用1，2，3，4能够组成多少个5位数，要求1出现2次或者3次，2出现0次或者1次，3没有限制，4只出现偶数次。

　　（x2/2!+x3/3!）（1+x）（1+x/1!+x2/2!+x3/3!+.....xk/k!+....）（1+x2/2!+x4/4!+......+x2n/(2n)!+......）

　　 每个式子的含义就不多解释了，读者应该能看懂它的含义。最终的结果就是x5/5!这一项的系数。

　　用代码去实现母函数的计算过程很简单，它是模拟我们人工计算多项式乘积的过程，比如有多项式H1*H2*H3......

　　我们先计算H1和H2的乘积，得到结果H'，再用H'和H3相乘......依次类推下去，直到得到最终的结果。

下面这道题目是航电上的一道题：

题目意思是有1分，2分，5分的硬币各a，b，c枚，求算不能组成的总钱数的最小值。

http://acm.hdu.edu.cn/showproblem.php?pid=1085

#include <iostream>
using namespace std;

int main(int argc, char *argv[])
{
    int num[3];
    int cent[3]={1,2,5};          //次数增长步长
    while(scanf("%d %d %d",&num[0],&num[1],&num[2]) != EOF)
    {
        if(num[0]==0&&num[1]==0&&num[2]==0)
            break;
        int i,j,k;
        int c[8001],tempC[8001];     //因为三种硬币最多1000枚，1*1000+2*1000+5*1000=8000，那么多项式乘积的最高次数为8000
                                     //c保存累计相乘各项的系数，tempC保存c和当前项相乘的系数
                                           //c[i] 表示次数为i的那一项的系数

         int max=num[0]+2*num[1]+5*num[2];   //求出该组输入条件下的最高次数 

         for(i=0;i<=8001;i++)
         {
            c[i]=0;
            tempC[i]=0;
         }

        //母函数为(1+x+x^2+...x^num[0])(1+x^2+x^4+....x^2*num[1])(1+x^5+x^10+...+x^5*num[2])
        for(i=0;i<=cent[0]*num[0];i+=cent[0])   //第一个多项式的系数初始化
        {
            c[i]=1;
        }

        for(i=1;i<3;i++)    //i表示总共有多少个多项式
        {
            for(j=0;j<=max;j++)    //累计相乘的x^j的系数
            {
                for(k=0;k+j<=max && k<=cent[i]*num[i];k+=cent[i])   //当前项x^k的系数
                {
                    tempC[k+j]+=c[j];   //x^j * x^k=x^(j+k)
                }
            }

            for(j=0;j<=max;j++)    //将临时数组清零
            {
                c[j]=tempC[j];
                tempC[j]=0;
            }
        }

        for(i=0;i<=max;i++)
        {
            if(c[i]==0)
                break;
        }
        printf("%d\n",i);
    }
    return 0;
}

作者：海子

　　　　
出处：http://www.cnblogs.com/dolphin0520/

　　　

时间： 2024-09-20 05:53:37

母函数与排列组合的相关文章

java-JAVA 生成 用0到9这十个数字 所有的排列组合（0不能再第一个）

问题描述 JAVA 生成 用0到9这十个数字 所有的排列组合(0不能再第一个) 用 0到9 生成 十位数的所有排列组合,数字0不能在第一个,这个生成的十位数, 不能有重复的数字. 解决方案 public static void main(String[] args) { String str[] = { "0", "1", "2", "3", "4", "5", "6"

C#非递归方式实现排列组合

C#以非递归方式实现三位排列组合,如下代码: //深度优先  class Program      {          static void Main(string[] args)          {              int[] number = new int[] { 1, 3, 5, 7 };              List data = new  List();              Stack openStack = new Stack();           

计算排列组合的php代码

前些天因为业务需要写了一段计算排列组合的代码,今天整理了一下,以备后用 <?php/** * 要解决的数学问题    :算出C(a,1) * C(b, 1) * ... * C(n, 1)的组合情况,其中C(n, 1)代表从n个元素里任意取一个元素 * * 要解决的实际问题样例:某年级有m个班级,每个班的人数不同,现在要从每个班里抽选一个人组成一个小组, *                       由该小组来代表该年级参加学校的某次活动,请给出所有可能的组合 */ /* ##########

浅析实现排列组合查询算法

所谓的排列组合查询就相当于GOOGLE高级查询中"包含以下全部的字词"查询,也就是说查询中必须包含所有查询关键词,而且他们的顺序可以是任意.以下程序段实现了这一功能.比如输入查询关键字:tom tina则最一般的情况是在程序中使用类似于"select sex from student where name like '%tom%tina%' or name like '%tina%tom%' ordered by age" 的查询语句实现以上的查询,因此如何得到'%

关于各种排列组合java算法实现方法

一.利用二进制状态法求排列组合,此种方法比较容易懂,但是运行效率不高,小数据排列组合可以使用 复制代码 代码如下: import java.util.Arrays; //利用二进制算法进行全排列 //count1:170187 //count2:291656 public class test { public static void main(String[] args) { long start=System.currentTimeMillis(); count2(); long end=S

PHP中排列组合及性能对比

  排列组合公式/排列组合计算公式公式P是指排列,从N个元素取R个进行排列. 公式C是指组合,从N个元素取R个,不进行排列了,但在php中我们可以用N种方法写出来了,但每一种写法的性能会不同,下面我们就来看看吧. 需求是这样的: 找到数组中所有可能的指定长度的组合,要求没有重复. 方法一: 代码如下   function getCombinationToString($arr,$m){ $result = array(); if ($m ==1){ return $arr; } if ($m =

字符 生成-简单的字符生成器-排列组合

问题描述 简单的字符生成器-排列组合 想要实现以下图片上的功能,上方选中我需要用的字母.数字,输入我需要生成的位数,最终列出所有的排列组合数据.求人帮忙,万分感谢. 解决方案 关键就是算法http://bbs.bccn.net/thread-347026-1-1.htmlhttp://outofmemory.cn/code-snippet/4237/c-pailie-zuhe-suanfa 解决方案二: 楼上说的对,关键就是排列组合的算法.最近做了有关排列组合的东西,代码是JAVA的,你是用什么

集合-排列组合 找真子集 不包含空集

问题描述 排列组合 找真子集 不包含空集 ** void solve(int cur_totalvar, int nextVar){ // 解决向量选择子集并求和 放到向量 for (int i = 0; i<cur_totalvar; ++i){ printf("%f ",num[i]); printf("chengchangshengn"); // ??? 放入变量 sunMombre.sun += num[i]; } if(cur_totalvar){

参数的排列组合3

如何获取排列组合的所有值呢? 之前咱们是求排列组合的取值个数,现在要求取值 首先我们考虑常规的情况: 我们有n个盒子,分别放置n个元素 第一回:我们从n个里面选择一个:有n种可能 第二回:我们从n-1个里面选择一个:有n-1种可能 第三回:我们从n-2个里面选择一个:有n-2种可能 第四回:我们从n-3个里面选择一个:有n-3种可能 -- 最后我们只有一个可选 直接上代码: /*** * @param base :[a,b,c,d] * @param times * @param remaini