精华内容
下载资源
问答
  • 字符串 abcd 要求输出组合为 a ab abc abcd b bc bcd c cd d 能不连续的情况出现 如何解决
  • 排列组合

    千次阅读 2018-10-01 18:17:08
    二、排列组合 排列: n个不同的元素中取m个元素按一定顺序排成一排 组合: n个不同的元素中取m个元素(不关心顺序问题) 解题小技巧:先组合排列 三、经典方法 1.捆绑法 如要求几个元素相邻,把他们合...

    一、核心原理

    加法原理

    乘法原理

    二、排列和组合

    排列:A_{n}^{m} =n*(n-1)*......*(n-m+1)

    n个不同的元素中取m个元素按一定顺序排成一排

    组合:C_{n}^{m} = \frac{A_{n}^{m}}{A_{m}^{m}}=\frac{n*(n-1)*......*(n-m+1)}{m*(m-1)*......*1}

    n个不同的元素中取m个元素(不关心顺序问题)

    解题小技巧:先组合再排列

    三、经典方法

    1.捆绑法

    如要求几个元素相邻,把他们合起来作为一个整体,在排列

    2.插空法

    要求元素不相邻,如ABCDEF排成一排,要求AB不相邻,则可以把CDEF先排好,把AB插进CDEF产生的5个空中就好

    3.插板法

    要求n个元素分成m个组,每个组必须要有一个元素时,可以在n个元素中产生的n-1个空中插m-1个板子

    4.留一法

    排列问题中,有元素的顺序已定,如alibaba全排列产生多少个字符串

    7个元素中a重复3次,b重复两次,则结果为元素全排除以重复元素的全排\frac{A_{7}^{7}}{A_{3}^{3}*A_{2}^{2}}

    5.分析对立面

    有的情况比较复杂,求相反面比较容易

    四、经典题目

    1.环形排列问题

    如n个人围成一个圈,共有多少种坐法    A_{n-1}^{n-1}

    2.错位重拍问题

    指n个元素的位置重新排列,使得每个元素不在自己原来的位置上

    有固定公式D_{n}=(n-1)*(D_{n-1}+D_{n-2})

    可以先记住前5项:0,1,2,9,44       (一封信的时候没有方案)

    展开全文
  • 排列组合讲解

    千次阅读 2015-02-07 09:56:57
    排列组合是组合学最基本的概念。所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。排列组合的中心问题是研究给定要求的排列和组合...
    排列组合是组合学最基本的概念。所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。 排列组合与古典概率论关系密切。
    组合数学中的一种
    [编辑义项名]
    排列组合
    概述  
    删除切换
    更换模版
    基本信息栏  
    (当前模板:其他)
    中文名    
    排列组合
    外文名    
    permutation and combination
    请参照项目说明填写。若某项不适合当前词条,可留空。
        
    类别
        
    组合数学中的一种
    适用范围
        
    数学
    发展历程

    [数学] 虽然数数始于以结计数的远古时代,由于那时人的智力的发展尚处于低级阶段,谈不上有什么技巧。随着人们对于数的了解和研究,在形成与数密切相关的数学分支的过程中,如数论、代数、函数论以至泛函的形成与发展,逐步地从数的多样性发现数数的多样性,产生了各种数数的技巧。

    同时,在人们对于形有了深入的了解和研究的基础上,在形成与形密切相关的各种数学分支的过程中,如几何学、拓扑学以至范畴论的形成与发展,逐步地从形的多样性也发现了数形的多样性,产生了各种数形的技巧。近代的集合论、数理逻辑等反映了潜在的数与形之间的结合。而现代的代数拓扑和代数几何等则将数与形密切地联系在一起了。这些,对于以数的技巧为中心课题的近代组合学的形成与发展都产生了而且还将会继续产生深刻的影响。

    由此观之,组合学与其他数学分支有着必然的密切联系。它的一些研究内容与方法来自各个分支也应用于各个分支。当然,组合学与其他数学分支一样也有其独特的研究问题与方法,它源于人们对于客观世界中存在的数与形及其关系的发现和认识。例如,中国古代的《易经》中用十个天干和十二个地支以六十为周期来记载月和年,以及在洛书河图中关于幻方的记载,是人们至今所了解的最早发现的组合问题甚或是架构语境学。

    于11和12世纪间,贾宪就发现了二项式系数,杨辉将它整理记载在他的《续古抉奇法》一书中。这就是中国通常称的杨辉三角。事实上,于12世纪印度的婆什迦罗第二也发现了这种组合数。13世纪波斯的哲学家曾讲授过此类三角。而在西方,布莱士·帕斯卡发现这个三角形是在17世纪中期。这个三角形在其他数学分支的应用也是屡见不鲜的。同时,帕斯卡和费马均发现了许多与概率论有关的经典组合学的结果。因此,西方人认为组合学开始于17世纪。组合学一词是德国数学家莱布尼茨在数学的意义下首次应用。也许,在那时他已经预感到了其将来的蓬勃发展。然而只有到了18世纪欧拉所处时代,组合学才可以说开始了作为一门科学的发展,因为那时,他解决了柯尼斯堡七桥问题,发现了多面体(首先是凸多面体,即平面图的情形)的顶点数、边数和面数之间的简单关系,被人们称为欧拉公式。甚至,当今人们所称的哈密顿圈的首创者也应该是欧拉。这些不但使欧拉成为组合学的一个重要组成部分——图论而且也成为占据现代数学舞台中心的拓扑学发展的先驱。同时,他对导致当今组合学中的另一个重要组成部分——组合设计中的拉丁方的研究所提出的猜想,人们称为欧拉猜想, [欧拉] 直到1959年才得到完全的解决。

    于19世纪初,高斯提出的组合系数,今称高斯系数,在经典组合学中也占有重要地位。同时,他还研究过平面上的闭曲线的相交问题,由此所提出的猜想称为高斯猜想,它直到20世纪才得到解决。这个问题不仅贡献于拓扑学,而且也贡献于组合学中图论的发展。同在19世纪,由乔治·布尔发现且被当今人们称为布尔代数的分支已经成为组合学中序理论的基石。当然,在这一时期,人们还研究其他许多组合问题,它们中的大多数是娱乐性的。

    20世纪初期,庞加莱联系多面体问题发展了组合学的概念与方法,导致了近代拓扑学从组合拓扑学到代数拓扑学的发展。于20世纪的中、后期,组合学发展之迅速也许是人们意想不到的。首先,于1920年费希尔(Fisher,R.A.)和耶茨(Yates,F.)发展了实验设计的统计理论,其结果导致后来的信息论,特别是编码理论的形成与发展.于1939年,坎托罗维奇(Канторович,Л.В.)发现了线性规划问题并提出解乘数法。于1947年丹齐克(Dantzig,G.B.)给出了一般的线性规划模型和理论,他所创立的单纯形方法奠定了这一理论的基础,阐明了其解集的组合结构。直到今天它仍然是应用得最广泛的数学方法之一。这些又导致以网络流为代表的运筹学中的一系列问题的形成与发展。开拓了人们目前称为组合最优化的一个组合学的新分支。在20世纪50年代,中国也发现并解决了一类称为运输问题的线性规划的图上作业法,它与一般的网络流理论确有异曲同工之妙。在此基础上又出现了国际上通称的中国邮递员问题。

    另一方面,自1940年以来,生于英国的塔特(Tutte,W.T.)在解决拼方问题中取得了一系列有关图论的结果,这些不仅开辟了现今图论发展的许多新研究领域,而且对于20世纪30年代,惠特尼(Whitney,H.)提出的拟阵论以及人们称之为组合几何的发展都起到了核心的推动作用。应该特别提到的是在这一时期,随着电子技术和计算机科学的发展愈来愈显示出组合学的潜在力量。同时,也为组合学的发展提出了许多新的研究课题。例如,以大规模和超大规模集成电路设计为中心的计算机辅助设计提出了层出不穷的问题。其中一些问题的研究与发展正在形成一种新的几何,人们称之为组合计算几何。关于算法复杂性的究,自1961年库克(Cook,S.A.)提出NP完全性理论以来,已经将这一思想渗透到组合学的各个分支以至数学和计算机科学中的一些分支。

    近20年来,用组合学中的方法已经解决了一些即使在整个数学领域也是具有挑战性的难题。例如,范·德·瓦尔登(Van der Waerden,B.L.)于1926年提出的关于双随机矩阵积和式猜想的证明;希伍德(Heawood,P.J.)于1890年提出的曲面地图着色猜想的解决;著名的四色定理的计算机验证和扭结问题的新组合不变量发现等。在数学中已经或正在形成着诸如组合拓扑、组合几何、组合数论、组合矩阵论、组合群论等与组合学密切相关的交叉学科。此外,组合学也正在渗透到其他自然科学以及社会科学的各个方面,例如,物理学、力学、化学、生物学、遗传学、心理学以及经济学、管理学甚至政治学等。

    1772年,法国数学家范德蒙德(Vandermonde, A. - T.)以[n]p表示由n个不同的元素中每次取p个的排列数。 [排列组合常见公式]

    瑞士数学家欧拉(Euler, L.)则于1771年以 及于1778年以 表示由n个不同元素中每次取出p个元素的组合数。

    1830年,英国数学家皮科克(Peacock, G)引入符号Cr表示n个元素中每次取r个的组合数。

    1869年或稍早些,剑桥的古德文以符号nPr 表示由n个元素中每次取r个元素的排列数,这用法亦延用至今。按此法,nPn便相当于n!。

    1872年,德国数学家埃汀肖森(Ettingshausen,B. A. von)引入了符号(np)来表示同样的意义,这组合符号(Signs of Combinations)一直沿用至今。

    1880年,鲍茨(Potts , R.)以nCr及nPr分别表示由n个元素取出r个的组合数与排列数。

    1886年,惠特渥斯(Whit-worth, A. W.)用Cnr和Pnr表示同样的意义,他还用Rnr表示可重复的组合数。

    1899年,英国数学家、物理学家克里斯托尔(Chrystal,G.)以nPr,nCr分别表示由n个不同元素中每次取出r个不重复之元素的排列数与组合数,并以nHr表示相同意义下之可重复的排列数,这三种符号也通用至今。

    1904年,德国数学家内托(Netto, E.)为一本百科辞典所写的辞条中,以Arn表示上述nPr之意,以Crn表示上述nCr之意,后者亦也用符号(n r)表示。这些符号也一直用到现代。

    此外,在八卦中,亦运用到了排列组合。
    定义及相关
    定义及公式

    [排列数公式]

    排列的定义及其计算公式:从n个不同元素中,任取m(m≤n,m与n均为自然数,下同)个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出m(m≤n)个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号 A(n,m)表示。A(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)! 此外规定0!=1(n!表示n(n-1)(n-2)...1,也就是6!=6x5x4x3x2x1

    组合的定义及其计算公式:从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出m(m≤n)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数。用符号 C(n,m) 表示。C(n,m)=A(n,m)/m!;C(n,m)=C(n,n-m)。(n≥m)

    其他排列与组合公式 从n个元素中取出m个元素的循环排列数=A(n,m)/m!=n!/m!(n-m)!. n个元素被分成k类,每类的个数分别是n1,n2,...nk这n个元素的全排列数为 n!/(n1!×n2!×...×nk!). k类元素,每类的个数无限,从中取出m个元素的组合数为C(m+k-1,m)。
    符号

    [常见的一道题目] C-Combination 组合数

    A-Arrangement排列数(在旧教材为P-Permutation)

    N-元素的总个数

    M-参与选择的元素个数

    !-阶乘
    基本计数原理

    ⑴加法原理和分类计数法

    ⒈加法原理:做一件事,完成它可以有n类办法,在第一类办法中有m1种不同的方法,在第二类办法中有m2种不同的方法,……,在第n类办法中有mn种不同的方法,那么完成这件事共有N=m1+m2+m3+…+mn种不同方法。

    ⒉第一类办法的方法属于集合A1,第二类办法的方法属于集合A2,……,第n类办法的方法属于集合An,那么完成这件事的方法属于集合A1UA2U…UAn。

    ⒊分类的要求 :每一类中的每一种方法都可以独立地完成此 [组合恒等式] 任务;两类不同办法中的具体方法,互不相同(即分类不重);完成此任务的任何一种方法,都属于某一类(即分类不漏)。

    ⑵乘法原理和分步计数法

    ⒈ 乘法原理:做一件事,完成它需要分成n个步骤,做第一步有m1种不同的方法,做第二步有m2种不同的方法,……,做第n步有mn种不同的方法,那么完成这件事共有N=m1×m2×m3×…×mn种不同的方法。

    ⒉合理分步的要求

    任何一步的一种方法都不能完成此任务,必须且只须连续完成这n步才能完成此任务;各步计数相互独立;只要有一步中所采取的方法不同,则对应的完成此事的方法也不同。

    3.与后来的离散型随机变量也有密切相关。
    二项式定理

    (a+b)^n=Σ(0->n)C(in)a^(n-i)b^i

    通项公式:a_(i+1)=C(in)a^(n-i)b^i

    二项式系数:C(in)杨辉三角:右图。两端是1,除1外的每个数是肩上两数之和。

    系数性质:

    ⑴和首末两端等距离的系数相等;

    ⑵当二项式指数n是奇数时,中间两项最大且相等;

    ⑶当二项式指数n是偶数时,中间一项最大;

    ⑷二项式展开式中奇数项和偶数项总和相同,都是2^(n-1);

    ⑸二项式展开式中所有系数总和是2^n
    组合数的奇偶

    奇偶定义:对组合数C(n,k)(n>=k):将n,k分别化为二进制,若某二进制位对应的n为0,而k为1 ,则C(n,k)为偶数;否则为奇数。

    下面是判定方法:

    结论:

    对于C(n,k),若n&k == k 则c(n,k)为奇数,否则为偶数。

    证明:

    对于C(n,k),若n&k == k 则c(n,k)为奇数,否则为偶数。

    证明:

    利用数学归纳法:

    由C(n,k) = C(n-1,k) + C(n-1,k-1);

    对应于杨辉三角:

    1

    1 1

    1 2 1

    1 3 3 1

    1 4 6 4 1

    ………………

    可以验证前面几层及k = 0时满足结论,下面证明在C(n-1,k)和C(n-1,k-1) (k > 0) 满足结论的情况下,

    C(n,k)满足结论。

    1).假设C(n-1,k)和C(n-1,k-1)为奇数:

    则有:(n-1)&k == k;

    (n-1)&(k-1) == k-1;

    由于k和k-1的最后一位(在这里的位指的是二进制的位,下同)必然是不同的,所以n-1的最后一位必然是1



    现假设n&k == k。

    则同样因为n-1和n的最后一位不同推出k的最后一位是1。

    因为n-1的最后一位是1,则n的最后一位是0,所以n&k != k,与假设矛盾。

    所以得n&k != k。

    2).假设C(n-1,k)和C(n-1,k-1)为偶数:

    则有:(n-1)&k != k;

    (n-1)&(k-1) != k-1;

    现假设n&k == k.

    则对于k最后一位为1的情况:

    此时n最后一位也为1,所以有(n-1)&(k-1) == k-1,与假设矛盾。

    而对于k最后一位为0的情况:

    则k的末尾必有一部分形如:10; 代表任意个0。

    相应的,n对应的部分为:1{*}*; *代表0或1。

    而若n对应的{*}*中只要有一个为1,则(n-1)&k == k成立,所以n对应部分也应该是10。

    则相应的,k-1和n-1的末尾部分均为01,所以(n-1)&(k-1) == k-1 成立,与假设矛盾。

    所以得n&k != k。

    由1)和2)得出当C(n,k)是偶数时,n&k != k。

    3).假设C(n-1,k)为奇数而C(n-1,k-1)为偶数:

    则有:(n-1)&k == k;

    (n-1)&(k-1) != k-1;

    显然,k的最后一位只能是0,否则由(n-1)&k == k即可推出(n-1)&(k-1) == k-1。

    所以k的末尾必有一部分形如:10;

    相应的,n-1的对应部分为:1{*}*;

    相应的,k-1的对应部分为:01;

    则若要使得(n-1)&(k-1) != k-1 则要求n-1对应的{*}*中至少有一个是0.

    所以n的对应部分也就为 :1{*}*; (不会因为进位变1为0)

    所以 n&k = k。

    4).假设C(n-1,k)为偶数而C(n-1,k-1)为奇数:

    则有:(n-1)&k != k;

    (n-1)&(k-1) == k-1;

    分两种情况:

    当k-1的最后一位为0时:

    则k-1的末尾必有一部分形如:10;

    相应的,k的对应部分为 : 11;

    相应的,n-1的对应部分为 : 1{*}0; (若为1{*}1,则(n-1)&k == k)

    相应的,n的对应部分为 : 1{*}1;

    所以n&k = k。

    当k-1的最后一位为1时:

    则k-1的末尾必有一部分形如:01; (前面的0可以是附加上去的)

    相应的,k的对应部分为 : 10;

    相应的,n-1的对应部分为 : 01; (若为11,则(n-1)&k == k)

    相应的,n的对应部分为 : 10;

    所以n&k = k。

    由3),4)得出当C(n,k)为奇数时,n&k = k。

    综上,结论得证。
    著名问题

        计算一些物品在特定条件下分组的方法数目。这些是关于排列、组合和整数分拆的。

        地图着色问题:对世界地图着色,每一个国家使用一种颜色。如果要求相邻国家的颜色相异,是否总共只需四种颜色?这是图论的问题。

        船夫过河问题:船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场,羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河?这是线性规划的问题。

        中国邮差问题:由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次,怎样行走走过的路程最短?这不是一个NP完全问题,存在多项式复杂度算法:先求出度为奇数的点,用匹配算法算出这些点间的连接方式,然后再用欧拉路径算法求解。这也是图论的问题。

        任务分配问题(也称婚配问题):有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少?这是线性规划的问题。

        如何构作幻方。

        大乐透

    例题分析
    难点

    ⑴从千差万别的实际问题中抽象出几种特定的数学模型,需要较强的抽象思维能力;

    ⑵限制条件有时比较隐晦,需要我们对问题中的关键性词(特别是逻辑关联词和量词)准确理解;

    ⑶计算手段简单,与旧知识联系少,但选择正确合理的计算方案时需要的思维量较大;

    ⑷计算方案是否正确,往往不可用直观方法来检验,要求我们搞清概念、原理,并具有较强的分析能力。
    例题

    【例1】 从1、2、3、……、20这二十个数中任取三个不同的数组成等差数列,这样的不同等差数列有多少个?

    分析:首先要把复杂的生活背景或其它数学背景转化为一个明确的排列组合问题。

    设a,b,c成等差,∴ 2b=a+c,可知b由a,c决定,

    又∵ 2b是偶数,∴ a,c同奇或同偶,即:分别从1,3,5,……,19或2,4,6,8,……,20这十个数中选出两个数进行排列,由此就可确定等差数列,A(10,2)*2=90*2,因而本题为180。

    【例2】 某城市有4条东西街道和6条南北的街道,街道之间的间距相同,若规定只能向东或向北两个方向沿图中路线前进,则从M到N有多少种不同的走法?

    分析:对实际背景的分析可以逐层深入:

    (一)从M到N必须向上走三步,向右走五步,共走八步;

    (二)每一步是向上还是向右,决定了不同的走法;

    (三)事实上,当把向上的步骤决定后,剩下的步骤只能向右;

    从而,任务可叙述为:从八个步骤中选出哪三步是向上走,就可以确定走法数。

    ∴ 本题答案为:C(8,3)=56。
    分析

    分析是分类还是分步,是排列还是组合

    注意加法原理与乘法原理的特点,分析是分类还是分步,是排列还是组合。

    【例3】在一块并排的10垄田地中,选择二垄分别种植A,B两种作物,每种种植一垄,为有利于作物生长,要求A,B两种作物的间隔不少于6垄,不同的选法共有多少种?

    分析:条件中“要求A、B两种作物的间隔不少于6垄”这个条件不容易用一个包含排列数,组合数的式子表示,因而采取分类的方法。

    第一类:A在第一垄,B有3种选择;

    第二类:A在第二垄,B有2种选择;

    第三类:A在第三垄,B有1种选择,

    同理A、B位置互换 ,共12种。

    【例4】从6双不同颜色的手套中任取4只,其中恰好有一双同色的取法有多少种?

    (A)240 (B)180 (C)120 (D)60

    分析:显然本题应分步解决。

    (一)从6双中选出一双同色的手套,有6种方法;

    (二)从剩下的十只手套中任选一只,有10种方法。

    (三)从除前所涉及的两双手套之外的八只手套中任选一只,有8种方法;

    (四)由于选取与顺序无关,因(二)(三)中的选法重复一次,因而共240种。

    或分步

    ⑴从6双中选出一双同色的手套,有C(6,1)=6种方法

    ⑵从剩下的5双手套中任选两双,有C(5,2)=10种方法

    ⑶从两双中手套中分别拿两只手套,有C(2,1)×C(2,1)=4种方法。

    同样得出共⑴×⑵×⑶=240种。

    【例5】.身高互不相同的6个人排成2横行3纵列,在第一行的每一个人都比他同列的身后的人个子矮,则所有不同的排法种数为_______。

    分析:每一纵列中的两人只要选定,则他们只有一种站位方法,因而每一纵列的排队方法只与人的选法有关系,共有三纵列,从而有C(6,2)×C(4,2)×C(2,2)=90种。

    【例6】在11名工人中,有5人只能当钳工,4人只能当车工,另外2人能当钳工也能当车工。现从11人中选出4人当钳工,4人当车工,问共有多少种不同的选法?

    分析:采用加法原理首先要做到分类不重不漏,如何做到这一点?分类的标准必须前后统一。

    以两个全能的工人为分类的对象,考虑以他们当中有几个去当钳工为分类标准。

    第一类:这两个人都去当钳工,C(2,2)×C(5,2)×C(4,4)=10种;

    第二类:这两个人都去当车工,C(5,4)×C(2,2)×C(4,2)=30种;

    第三类:这两人既不去当钳工,也不去当车工C(5,4)×C(4,4)=5种。

    第四类:这两个人一个去当钳工、一个去当车工,C(2,1)×C(5,3)×C(4,3)=80种;

    第五类:这两个人一个去当钳工、另一个不去当车工,C(2,1)×C(5,3)×C(4,4)=20种;

    第六类:这两个人一个去当车工、另一个不去当钳工,C(5,4)×C(2,1)×C(4,3)=40种;

    因而共有185种。

    【例7】现有印着0,1,3,5,7,9的六张卡片,如果允许9可以作6用,那么从中任意抽出三张可以组成多少个不同的三位数?

    分析:有同学认为只要把0,1,3,5,7,9的排法数乘以2即为所求,但实际上抽出的三个数中有9的话才可能用6替换,因而必须分类。

    抽出的三数含0,含9,有32种方法;

    抽出的三数含0不含9,有24种方法;

    抽出的三数含9不含0,有72种方法;

    抽出的三数不含9也不含0,有24种方法。

    因此共有32+24+72+24=152种方法。

    【例8】停车场划一排12个停车位置,今有8辆车需要停放,要求空车位连在一起,不同的停车方法有多少种?

    分析:把空车位看成一个元素,和8辆车共九个元素排列,因而共有A(9,9)=362880种停车方法。
    特殊优先

    特殊元素,优先处理;特殊位置,优先考虑。

    【例9】六人站成一排,求

    ⑴甲、乙既不在排头也不在排尾的排法数

    ⑵甲不在排头,乙不在排尾,且甲乙不相邻的排法数

    分析:⑴按照先排出首位和末尾再排中间四位分步计数

    第一步:排出首位和末尾、因为甲乙不在首位和末尾,那么首位和末尾实在其它四位数选出两位进行排列、一共有A(4,2)=12种;

    第二步:由于六个元素中已经有两位排在首位和末尾,因此中间四位是把剩下的四位元素进行顺序排列,

    共A(4,4)=24种;

    根据乘法原理得即不再排头也不在排尾数共12×24=288种。

    ⑵第一类:甲在排尾,乙在排头,有A(4,4)种方法。

    第二类:甲在排尾,乙不在排头,有3×A(4,4)种方法。

    第三类:乙在排头,甲不在排尾,有3×A(4,4)种方法。

    第四类:甲不在排尾也不在排头,乙不在排头也不在排尾,有6×A(4,4)种方法(排除相邻)。

    共A(4,4)+3×A(4,4)+3×A(4,4)+6×A(4,4)=312种。

    【例10】对某件产品的6件不同正品和4件不同次品进行一一测试,至区分出所有次品为止。若所有次品恰好在第五次测试时被全部发现,则这样的测试方法有多少种可能?

    分析:本题意指第五次测试的产品一定是次品,并且是最后一个次品,因而第五次测试应算是特殊位置了,分步完成。

    第一步:第五次测试的有C(4,1)种可能;

    第二步:前四次有一件正品有C(6,1)中可能。

    第三步:前四次有A(4,4)种可能。

    ∴ 共有576种可能。
    捆绑与插空

    【例11】8人排成一队

    ⑴甲乙必须相邻

    ⑵甲乙不相邻

    ⑶甲乙必须相邻且与丙不相邻

    ⑷甲乙必须相邻,丙丁必须相邻

    ⑸甲乙不相邻,丙丁不相邻

    分析:⑴甲乙必须相邻,就是把甲乙 捆绑(甲乙可交换) 和7人排列A(7,7)×A(2,2)

    ⑵甲乙不相邻,A(8,8)-A(7,7)×2。或A(6,6)×A(7,2)

    ⑶甲乙必须相邻且与丙不相邻,先求甲乙必须相邻且与丙相邻A(6,6)×2×2

    甲乙必须相邻且与丙不相邻A(7,7)×2-A(6,6)×2×2

    ⑷甲乙必须相邻,丙丁必须相邻A(6,6)×2×2

    ⑸甲乙不相邻,丙丁不相邻,A(8,8)-A(7,7)×2×2+A(6,6)×2×2

    【例12】某人射击8枪,命中4枪,恰好有三枪连续命中,有多少种不同的情况?

    分析:∵ 连续命中的三枪与单独命中的一枪不能相邻,因而这是一个插空问题。另外没有命中的之间没有区别,不必计数。即在四发空枪之间形成的5个空中选出2个的排列,即A(5,2)。

    【例13】 马路上有编号为l,2,3,……,10 十个路灯,为节约用电又看清路面,可以把其中的三只灯关掉,但不能同时关掉相邻的两只或三只,在两端的灯也不能关掉的情况下,求满足条件的关灯方法共有多少种?

    分析:即关掉的灯不能相邻,也不能在两端。又因为灯与灯之间没有区别,因而问题为在7盏亮着的灯形成的不包含两端的6个空中选出3个空放置熄灭的灯。∴ 共C(6,3)=20种方法。

    方法二:

    把其中的3只灯关掉总情况有C(8,3)种

    关掉相邻的三只有C(6,1)种

    关掉相邻的两只有2*C(7,2)-12种
      所以满足条件的关灯方法有:
      C(8,3)-C(6,1)-[2*C(7,2)-12]
      =56-6-(42-12)
      =20种
    间接计数法

    ⑴排除法

    【例14】三行三列共九个点,以这些点为顶点可组成多少个三角形?

    分析:有些问题正面求解有一定困难,可以采用间接法。

    所求问题的方法数=任意三个点的组合数-共线三点的方法数,

    ∴ 共76种。

    【例15】正方体8个顶点中取出4个,可组成多少个四面体?

    分析:所求问题的方法数=任意选四点的组合数-共面四点的方法数,

    ∴ 共C(8,4)-12=70-12=58个。

    【例16】1,2,3,……,9中取出两个分别作为对数的底数和真数,可组成多少个不同数值的对数?

    分析:由于底数不能为1。

    ⑴当1选上时,1必为真数,∴ 有一种情况。

    ⑵当不选1时,从2--9中任取两个分别作为底数,真数,共A(8,2)=56,其中log2为底4=log3为底9,log4为底2=log9为底3,log2为底3=log4为底9,log3为底2=log9为底4.

    因而一共有56-4+1=53个。

    【例17】 六人排成一排,要求甲在乙的前面,(不一定相邻),共有多少种不同的方法? 如果要求甲乙丙按从左到右依次排列呢?

    分析:(一)实际上,甲在乙的前面和甲在乙的后面两种情况对称,具有相同的排法数。因而有A(6,6)/2=360种。

    (二)先考虑六人全排列A(6,6)种;其次甲乙丙三人实际上只能按照一种顺序站位,因而前面的排法数重复了A(3,3)种, ∴ 有A(6,6)/A(3,3)=120种。

    【例18】5男4女排成一排,要求男生必须按从高到矮的顺序,共有多少种不同的方法?

    分析:首先不考虑男生的站位要求,共A(9,9)种;男生从左至右按从高到矮的顺序,只有一种站法,因而上述站法重复了A(5,5)次。因而有A(9,9,)/A(5,5,)=9×8×7×6=3024种

    若男生从右至左按从高到矮的顺序,只有一种站法, 同理也有3024种,综上,有6048种。

    【例19】 三个相同的红球和两个不同的白球排成一行,共有多少种不同的方法?

    分析:先认为三个红球互不相同,共A(5,5)=120种方法。

    而由于三个红球所占位置相同的情况下,共A(3,3)=6变化,因而共A(5,5)/A(3,3)=20种。

    公式P是指排列,从N个元素取R个进行排列(即排序)。(P是旧用法,教材上多用A,Arrangement)

    公式C是指组合,从N个元素取R个,不进行排列(即不排序)。
    挡板的使用

    【例20】10个名额分配到八个班,每班至少一个名额,问有多少种不同的分配方法?

    分析:把10个名额看成十个元素,在这十个元素之间形成的九个空中,选出七个位置放置档板,则每一种放置方式就相当于一种分配方式。因而共36种。
    区别与联系

    所有的排列都可以看作是先取组合,再做全排列;同样,组合如补充一个阶段(排序)可转化为排列问题。

    【例21】用数字0,1,2,3,4,5组成没有重复数字的四位数,

    ⑴可组成多少个不同的四位数?

    ⑵可组成多少个不同的四位偶数

    ⑶可组成多少个能被3整除的四位数?

    分析:⑴有A(6,4)-A(5,3)=300个。

    ⑵分为两类:0在末位,则有A(5,3)=60种:0不在末位,则有C(2,1)×A(5,3)-C(2,1)×A(4,2)=96种。

    ∴ 共60+96=156种。

    ⑶先把四个相加能被3整除的四个数从小到大列举出来,即先选

    0,1,2,3

    0,1,3,5

    0,2,3,4

    0,3,4,5

    1,2,4,5

    它们排列出来的数一定可以被3整除,再排列,有:4×[A(4,4)-A(3,3)]+A(4,4)=96种。
    分组问题

    【例22】 5名学生分配到4个不同的科技小组参加活动,每个科技小组至少有一名学生参加,则分配方法共有多少种?

    分析:(一)先把5个学生分成二人,一人,一人,一人各一组。

    其中涉及到平均分成四组,有C(5,3)=10种分组方法。可以看成4个板三个板不空的隔板法。

    (二)再考虑分配到四个不同的科技小组,有A(4,4)=24种,

    由(一)(二)可知,共10×24=240种。
    几何问题

    【例23】某区有7条南北向街道,5条东西向街道(如右图)

    ⑴图中共有多少个矩形?

    ⑵从A点到B点最近的走法有多少种?

    分析:⑴在7条竖线中任选2条,5条横线中任选2条,这样4条线

    可组成1个矩形,故可组成矩形C(7,2)·C(5,2)=210个

    ⑵每条东西向的街道被分成4段,每条南北向的街道被分成6段,从A到B最短的走法,无论怎样走,一定包括10段,其中6段方向相同,另外4段方向相同,每种走法,即是从10段中选出6段,这6段是走东西方向的,共有C(10,6)=C(10,4)=210种走法(同样可以从10段中选出4段走南北方向,每一种选法即是1种走法)。所以共有210种走法。
    口诀

    排列、组合、二项式定理公式口诀:

    加法乘法两原理,贯穿始终的法则。与序无关是组合,要求有序是排列。

    两个公式两性质,两种思想和方法。归纳出排列组合,应用问题须转化。

    排列组合在一起,先选后排是常理。特殊元素和位置,首先注意多考虑。

    不重不漏多思考,捆绑插空是技巧。排列组合恒等式,定义证明建模试。

    关于二项式定理,中国杨辉三角形。两条性质两公式,函数赋值变换式。
    展开全文
  • 排列组合公式及排列组合算法

    万次阅读 多人点赞 2014-03-27 09:38:32
    排列组合公式 排列组合公式/排列组合计算公式 公式P是指排列,从N个元素取M个进行排列。 公式C是指组合,从N个元素取M个进行组合,不进行排列。 N-元素的总个数 M参与选择的元素个数 !-阶乘,如 9...


    排列组合公式

    排列组合公式/排列组合计算公式

    公式P是指排列,从N个元素取M个进行排列。
    公式C是指组合,从N个元素取M个进行组合,不进行排列。
    N-元素的总个数
    M参与选择的元素个数
    !-阶乘,如    9!=9*8*7*6*5*4*3*2*1

    从N到数M个,表达式应该为n*(n-1)*(n-2)..(n-m+1);

                   因为从n到(n-m+1)个数为n-(n-m+1)=m

     

    举例:

    Q1:    有从1到9共计9个号码球,请问,可以组成多少个三位数?

    A1:    123和213是两个不同的排列数。即对排列顺序有要求的,既属于“排列P”计算范畴。

          上问题中,任何一个号码只能用一次,显然不会出现988,997之类的组合,我们可以这么看,百位数有9种可能,十位数则应该有9-1种可能,个位数则应该只有9-1-1种可能,最终共有9*8*7个三位数。计算公式=P(3,9)=9*8*7,(从9倒数3个的乘积)

     

    Q2:   有从1到9共计9个号码球,请问,如果三个一组,代表“三国联盟”,可以组合成多少个“三国联盟”?

    A2:    213组合和312组合,代表同一个组合,只要有三个号码球在一起即可。即不要求顺序的,属于“组合C”计算范畴。

           上问题中,将所有的包括排列数的个数去除掉属于重复的个数即为最终组合数C(3,9)=9*8*7/3*2*1


    排列组合算法


    1、最近一直在考虑从n个数里面取m个数的算法。最容易理解的就是递归,但是其效率实在不能使用。一直找寻中,今日得果

    2、算法来源与互联网

    组合算法  

      本程序的思路是开一个数组,其下标表示1到n个数,数组元素的值为1表示其下标代表的数被选中,为0则没选中。    
      首先初始化,将数组前m个元素置1,表示第一个组合为前m个数。 然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合

      后将其变为“01”组合,同时将其左边的所有“1”全部移动到数组的最左端。     当第一个“1”移动到数组的n-m的位置,即m个“1”全部移动到最右端时,就得   到了最后一个组合。    
      例如求5中选3的组合:    
      1   1   1   0   0   //1,2,3    
      1   1   0   1   0   //1,2,4    
      1   0   1   1   0   //1,3,4    
      0   1   1   1   0   //2,3,4    
      1   1   0   0   1   //1,2,5    
      1   0   1   0   1   //1,3,5    
      0   1   1   0   1   //2,3,5    
      1   0   0   1   1   //1,4,5    
      0   1   0   1   1   //2,4,5    
      0   0   1   1   1   //3,4,5  

    全排列算法  

      
      从1到N,输出全排列,共N!条。  
      分析:用N进制的方法吧。设一个N个单元的数组,对第一个单元做加一操作,满N进  
      一。每加一次一就判断一下各位数组单元有无重复,有则再转回去做加一操作,没  
      有则说明得到了一个排列方案。


    递归算法
        全排列是将一组数按一定顺序进行排列,如果这组数有n个,那么全排列数为n!个。现以{1, 2, 3, 4, 5}为
    例说明如何编写全排列的递归算法。
    1、首先看最后两个数4, 5。 它们的全排列为4 5和5 4, 即以4开头的5的全排列和以5开头的4的全排列。
    由于一个数的全排列就是其本身,从而得到以上结果。
    2、再看后三个数3, 4, 5。它们的全排列为3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六组数。
    即以3开头的和4,5的全排列的组合、以4开头的和3,5的全排列的组合和以5开头的和3,4的全排列的组合.
    从而可以推断,设一组数p = {r1, r2, r3, ... ,rn}, 全排列为perm(p),pn = p - {rn}。
    因此perm(p) = r1perm(p1),  r2perm(p2),  r3perm(p3), ... ,  rnperm(pn)。当n = 1时perm(p} = r1。
    为了更容易理解,将整组数中的所有的数分别与第一个数交换,这样就总是在处理后n-1个数的全排列。
    算法如下:
    #include <stdio.h>
    int n = 0;
    void swap(int *a, int *b){
        int m;
        m = *a;
        *a = *b;
        *b = m;
    }
    void perm(int list[], int k, int m){
        int i;
        if(k > m) {
            for(i = 0; i <= m; i++)
                printf("%d ", list[i]);
            printf("/n");
            n++;
        } else {
            for(i = k; i <= m; i++) {
                swap(&list[k], &list[i]);
                perm(list, k + 1, m);
                swap(&list[k], &list[i]);
            }
        }
    }
    int main(){
        int list[] = {1, 2, 3, 4, 5};
        perm(list, 0, 4);
        printf("total:%d/n", n);
        return 0;
    }

    谁有更高效的递归和非递归算法。

    全排序
    设R={r1,r2,...,rn}是要进行排列的n个元素,Ri = R-{ri}. 集合 X 中元素的全排列记为Perm(X)。(ri) Perm(X)表示在全排列Perm(X)的每一个排列上加前缀ri得到的排列。R的全排列可归纳定义如下:
    当 n = 1 时, Perm(R) = (r), 其中r 是集合R中唯一的元素;
    当 n > 1 时, Perm(R)有 (r1)Perm(R1), (r2)Perm(R2),.......,(rn)Perm(Rn) 构成
    依此递归定义,可设计产生Perm(R)的递归算法如下:
    template <class Type>
    void Perm(Type list[], int k, int m){
        if ( k == m ){
            for ( int i = 0; i <= m; i++)
                        cout << list[i];
            cout << endl;
        } else {
            for ( int i = k; i <= m; i ++){
               Swap(list[k],        list[i] );
               Perm( list,k + 1,  m ) ;
               Swap( list[k],       list[i] );
             }
        }
    }

    template < class Type > inline void Swap ( Type &a ,Type & b) {
             Type temp = a; a = b; b = temp;
    }


    排列组合问题的通用算法

        尽管排列组合是生活中经常遇到的问题,可在程序设计时,不深入思考或者经验不足都让人无从下手。由于排列组合问题总是先取组合再排列,并且单纯的排列问题相对简单,所以本文仅对组合问题的实现进行详细讨论。以在n个数中选取m(0<m<=n)个数为例,问题可分解为:
    1. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止。
    2. 从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m。
    很明显,上述方法是一个递归的过程,也就是说用递归的方法可以很干净利索地求得所有组合。
    下面是递归方法的实现:
    /// 求从数组a[1..n]中任选m个元素的所有组合。
    /// a[1..n]表示候选集,m表示一个组合的元素个数。
    /// b[1..M]用来存储当前组合中的元素, 常量M表示一个组合中元素的个数。
    void combine( int a[], int n, int m,  int b[], const int M )
    {
     for(int i=n; i>=m; i--)  // 注意这里的循环范围
     {
          b[m-1] = i - 1;
          if (m > 1)
               combine(a,i-1,m-1,b,M);
          else      // m == 1, 输出一个组合
          {  
               for(int j=M-1; j>=0; j--)
                cout << a[b[j]] << " ";
           cout << endl;
          }
     }
    }
    因为递归程序均可以通过引入栈,用回溯转化为相应的非递归程序,所以组合问题又可以用回溯的方法来解决。为了便于理解,我们可以把组合问题化归为图的路径遍历问题,在n个数中选取m个数的所有组合,相当于在一个这样的图中(下面以从1,2,3,4中任选3个数为例说明)求从[1,1]位置出发到达[m,x] (m<=x<=n)位置的所有路径:
    1  2  3  4
        2  3  4
            3  4
    上图是截取n×n右上对角矩阵的m行构成,我们要求的所有组合就相当于从第一行的第一列元素[1,1]出发,到第三行的任意一列元素作为结束的所有路径,规定每走一步需跨越一行,并且从上一行的任何一个元素到其下一行中列处于其右面的任何一个元素均有一路径相连,显然任一路径经过的数字序列就对应一个符合要求的组合。
    下面是非递归的回溯方法的实现:
    /// 求从数组a[1..n]中任选m个元素的所有组合。
    /// a[1..n]表示候选集,m表示一个组合的元素个数。
    /// 返回所有排列的总数。
    int combine(int a[], int n, int m){
     m = m > n ? n : m;
     int* order = new int[m+1];
     for(int i=0; i<=m; i++)
      order[i] = i-1;            // 注意这里order[0]=-1用来作为循环判断标识

     int count = 0;                              
     int k = m;
     bool flag = true;           // 标志找到一个有效组合
     while(order[0] == -1)
     {
          if(flag)                   // 输出符合要求的组合
          {
               for(i=1; i<=m; i++)
                cout << a[order[i]] << " ";
           cout << endl;
           count++;
           flag = false;
          }

          order[k]++;                // 在当前位置选择新的数字
          if(order[k] == n)          // 当前位置已无数字可选,回溯
          {
           order[k--] = 0;
           continue;
          }
        
          if(k < m)                  // 更新当前位置的下一位置的数字        
          {
           order[++k] = order[k-1];
           continue;
          }

          if(k == m)
           flag = true;
     }
     delete[] order;
     return count;
    }

    下面是测试以上函数的程序:
    int main()
    {
     const int N = 4;
     const int M = 3;
     int a[N];
     for(int i=0;i<N;i++)
      a[i] = i+1;

     // 回溯方法
     cout << combine(a,N,3) << endl;

     // 递归方法
     int b[M];
     combine(a,N,M,b,M);

     return 0;
    }

    由上述分析可知,解决组合问题的通用算法不外乎递归和回溯两种。在针对具体问题的时候,因为递归程序在递归层数上的限制,对于大型组合问题而言,递归不是一个好的选择,这种情况下只能采取回溯的方法来解决。

        n个数的全排列问题相对简单,可以通过交换位置按序枚举来实现。STL提供了求某个序列下一个排列的算法next_permutation,其算法原理如下:
    1. 从当前序列最尾端开始往前寻找两个相邻元素,令前面一个元素为*i,后一个元素为*ii,且满足*i<*ii;
    2. 再次从当前序列末端开始向前扫描,找出第一个大于*i的元素,令为*j(j可能等于ii),将i,j元素对调;
    3. 将ii之后(含ii)的所有元素颠倒次序,这样所得的排列即为当前序列的下一个排列。
    其实现代码如下:
    template <class BidirectionalIterator>
    bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
    {
      if (first == last) return false;   // 空範圍
      BidirectionalIterator i = first;
      ++i;
      if (i == last) return false;       // 只有一個元素
      i = last;                          // i 指向尾端
      --i;

     for(;;)
     {
      BidirectionalIterator ii = i;
      --i;
      // 以上,鎖定一組(兩個)相鄰元素
      if (*i < *ii)                     // 如果前一個元素小於後一個元素
      {
       BidirectionalIterator j = last;  // 令 j指向尾端
       while (!(*i < *--j));            // 由尾端往前找,直到遇上比 *i 大的元素
       iter_swap(i, j);                 // 交換 i, j
       reverse(ii, last);               // 將 ii 之後的元素全部逆向重排
       return true;
      }
      if (i == first)                   // 進行至最前面了
      {
       reverse(first, last);            // 全部逆向重排
       return false;
      }
     }
    }

    下面程序演示了利用next_permutation来求取某个序列全排列的方法:
    int main()
    {
     int ia[] = {1,2,3,4};
     vector<int> iv(ia,ia+sizeof(ia)/sizeof(int));

     copy(iv.begin(),iv.end(),ostream_iterator<int>(cout," "));
     cout << endl;
     while(next_permutation(iv.begin(),iv.end()))
     {
      copy(iv.begin(),iv.end(),ostream_iterator<int>(cout," "));
      cout << endl;
     }

     return 0;
    }
    注意:上面程序中初始序列是按数值的从小到大的顺序排列的,如果初始序列无序的话,上面程序只能求出从当前序列开始的后续部分排列,也就是说next_permutation求出的排列是按排列从小到大的顺序进行的。

    ///

    排列组合与回溯算法

    KuiBing

    感谢Bamboo、LeeMaRS的帮助

    [关键字] 递归 DFS

    [前言] 这篇论文主要针对排列组合对回溯算法展开讨论,在每一个讨论之后,还有相关的推荐题。在开始之前,我们先应该看一下回溯算法的概念,所谓回溯:就是搜索一棵状态树的过程,这个过程类似于图的深度优先搜索(DFS),在搜索的每一步(这里的每一步对应搜索树的第i层)中产生一个正确的解,然后在以后的每一步搜索过程中,都检查其前一步的记录,并且它将有条件的选择以后的每一个搜索状态(即第i+1层的状态节点)。

    需掌握的基本算法:

    排列:就是从n个元素中同时取r个元素的排列,记做P(n,r)。(当r=n时,我们称P(n,n)=n!为全排列)例如我们有集合OR = {1,2,3,4},那么n = |OR| = 4,切规定r=3,那么P(4,3)就是:

    {1,2,3}; {1,2,4}; {1,3,2}; {1,3,4};{1,4,2};{1,4,3};{2,1,3};{2,1,4}; {2,3,1}; {2,3,4}; {2,4,1}; {2,4,3}; {3,1,2}; {3,1,4}; {3,2,1}; {3,2,4}; {3,4,1}; {3,4,2}; {4,1,2}; {4,1,3}; {4,2,1}; {4,2,3}; {4,3,1}; {4,3,2}

    算法如下:

    int  n, r;
    char used[MaxN];
    int  p[MaxN];
     
    void permute(int pos)
    { int i;
    /*如果已是第r个元素了,则可打印r个元素的排列 */
        if (pos==r) {
            for (i=0; i<r; i++)
                cout << (p[i]+1);
            cout << endl;
            return;
        }
        for (i=0; i<n; i++)
            if (!used[i]) { /*如果第i个元素未用过*/
    /*使用第i个元素,作上已用标记,目的是使以后该元素不可用*/
                used[i]++;
    /*保存当前搜索到的第i个元素*/
                p[pos] = i;
    /*递归搜索*/
               permute(pos+1);
     
    /*恢复递归前的值,目的是使以后改元素可用*/
     used[i]--;
            }
    }

    相关问题
    UVA 524 Prime Ring Problem

     

    可重排列:就是从任意n个元素中,取r个可重复的元素的排列。例如,对于集合OR={1,1,2,2}, n = |OR| = 4, r = 2,那么排列如下:

    {1,1}; {1,2}; {1,2}; {1,1}; {1,2}; {1,2}; {2,1}; {2,1}; {2,2}; {2,1}; {2,1}; {2,2}

    则可重排列是:

    {1,1}; {1,2}; {2,1}; {2,2}.

    算法如下:

    #define FREE -1
    int n, r;
    /*使元素有序*/
    int E[MaxN] = {0,0,1,1,1};
    int P[MaxN];
    char used[MaxN];
     
    void permute(int pos)
    {
    int i;
    /*如果已选了r个元素了,则打印它们*/
        if (pos==r)  {
            for (i=0; i<r; i++)
                cout << P[i];
            cout << endl;
            return;
        }
    /*标记下我们排列中的以前的元素表明是不存在的*/
        P[pos] = FREE;
        for (i=0; i<n; i++)
    /*如果第I个元素没有用过,并且与先前的不同*/
            if (!used[i] && E[i]!=P[pos]) {
    /*使用这个元素*/
                used[i]++;
    /*选择现在元素的位置*/
                P[pos] = E[i];
    /*递归搜索*/
                permute(pos+1);
    /*恢复递归前的值*/
                used[i]--;
            }
    }

    相关习题
    UVA 10098 Generating Fast, Sorted Permutations

     

    组合:从n个不同元素中取r个不重复的元素组成一个子集,而不考虑其元素的顺序,称为从n个中取r个的无重组合,例如OR = {1,2,3,4}, n = 4, r = 3则无重组合为:

    {1,2,3}; {1,2,4}; {1,3,4}; {2,3,4}.

    算法如下:

    int n, r;
    int C[5];
    char used[5];
     
    void combine(int pos, int h)
    {
    int i;
    /*如果已选了r个元素了,则打印它们*/
        if (pos==r) {
            for (i=0; i<r; i++)
                cout<< C[i];
            cout<< endl;
            return;
        }
        for (i=h; i<=n-r+pos; i++) /*对于所有未用的元素*/
            if (!used[i]) {
    /*把它放置在组合中*/
                C[pos] = i;
    /*使用该元素*/
     used[i]++;
    /*搜索第i+1个元素*/
         combine(pos+1,i+1);
    /*恢复递归前的值*/
     used[i]--;
            }
    }

    相关问题:
    Ural 1034 Queens in peaceful position

     

    可重组合:类似于可重排列。

    [例] 给出空间中给定n(n<10)个点,画一条简单路径,包括所有的点,使得路径最短。

    解:这是一个旅行售货员问题TSP。这是一个NP问题,其实就是一个排列选取问题。

    算法如下:

    int  n, r;
    char used[MaxN];
    int  p[MaxN];
    double min;
     
    void permute(int pos, double dist)
    {
    int i;
        if (pos==n) {
            if (dist < min) min = dist;
            return;
        }
        for (i=0; i<n; i++)
            if (!used[i]) {
                used[i]++;
                p[pos] = i;
               if (dist + cost(point[p[pos-1]], point[p[pos]]) < min)
                    permute(pos+1, dist + cost(point[p[pos-1]], point[p[pos]]));
     used[i]--;
            }
    }

    [例]对于0和1的所有排列,从中同时选取r个元素使得0和1的数量不同。

    解 这道题很简单,其实就是从0到2^r的二元表示。

    算法如下:

    void dfs(int pos)
    {
       if (pos == r)
       {
           for (i=0; i<r; i++) cout<<p[i];
           cout<<endl;
           return;
       }
       p[pos] = 0;
       dfs(pos+1);
       p[pos] = 1;
       dfs(pos+1);}

    相关问题:

    Ural

    1005 Stone pile
    1060 Flip Game
    1152 The False Mirrors

     

    [例]找最大团问题。

    一个图的团,就是包括了图的所有点的子图,并且是连通的。也就是说,一个子图包含了n个顶点和n*(n-1)/2条边,找最大团问题是一个NP问题。算法如下:

    #define MaxN 50
     
    int  n, max;
    int  path[MaxN][MaxN];
    int  inClique[MaxN];
     
    void dfs(int inGraph[])
    {
    int i, j;
    int Graph[MaxN];
     
    if ( inClique[0]+inGraph[0]<=max ) return;
    if ( inClique[0]>max ) max=inClique[0];
     
    /*对于图中的所有点*/
        for (i=1; i<=inGraph[0]; i++)
        {
    /*把节点放置到团中*/
            ++inClique[0];
     inClique[inClique[0]]=inGraph[i];
    /*生成一个新的子图*/
     Graph[0]=0;
     for (j=i+1; j<=inGraph[0]; j++)
         if (path[inGraph[i]][inGraph[j]] )
              Graph[++Graph[0]]=inGraph[j];
         dfs(Graph);
    /*从团中删除节点*/
            --inClique[0];}
    }
    int main()
    {
    int inGraph[MaxN];
    int i, j;
      cin >>n;
      while (n > 0)
      {
            for (i=0; i<n; i++)
     for (j=0; j<n; j++)
         cin >>path[i][j];
            max = 1;
    /*初始化*/
            inClique[0]= 0;
            inGraph[0] = n;
     for (i=0; i<n; i++) inGraph[i+1]=i;
            dfs(inGraph);
            cout<<max<<endl;
            cin >>n;
      }
      return 0;}

     

     参考论文 <A fast algorithm for the maximum clique problem>

    相关问题:

    acm.zju.edu.cn: 1492 maximum clique

     

    相关网站

    http://acm.uva.es/p

    http://acm.timus.ru/

     

    Contact me:

    MSN: Bing0672@Hotmail.com

    /

      求集合子集,和全排列的递归算法实现(c++,Dev C++调试通过)


    求集合全排列算法实现:

    求集合所有子集的算法实现:

    1.求集合全排列算法实现:

    /*
      Name:
      Copyright:
      Author: XuLei
      Date: 01-11-05 09:40
      Description:求一个字符串集合(List)的全排列,一共有n!种(假设字符数为n)
      Algorithms:令E= {e1 , ..., en }表示n 个元素的集合,我们的目标是生成该集合的所有排列方式。令Ei
                 为E中移去元素i 以后所获得的集合,perm (X) 表示集合X 中元素的排列方式,ei.p e r m
                 (X)表示在perm (X) 中的每个排列方式的前面均加上ei 以后所得到的排列方式。例如,如果
                 E={a, b, c},那么E1={b, c},perm (E1 )=( b c, c b),e1 .perm(E1) = (a b c, a c b)。
                 对于递归的基本部分,采用n = 1。当只有一个元素时,只可能产生一种排列方式,所以
                 perm (E) = (e),其中e 是E 中的唯一元素。当n > 1时,perm (E) = e1 .perm(E1) +e2 .p e r m
                 (E2) +e3.perm(E3) + ... +en .perm (En)。这种递归定义形式是采用n 个perm(X) 来定义perm(E),
                 其中每个X 包含n-1个元素。至此,一个完整的递归定义所需要的基本部分和递归部分都已完成。
    */
    #include <iostream>
    using namespace std;
    //const int ListLength=10;
    const int ListLength=3;     //字符串数组的长度
    void Swap(char &c, char &s) //交换字符c和s
    {
         char temp=c;
         c=s;
         s=temp;
    }
    void Perm(char *List, int m, int k)
    {
         static int count=0;
         if(m==k)
         {
                 cout<<++count<<":";
                 for(int i=0; i<=ListLength-1; i++)
                 {
                         cout<<List[i];
                 }           
                 cout<<endl;
         }
         else
         {
             for(int i=m; i<=k; i++)
             {
                      Swap(List[m],List[i]);
                      Perm(List, m+1, k);
                      Swap(List[m],List[i]);
                    
             }       
         }
           
    }
    int main()
    {
        //char List[ListLength]={'a','b','c','d','e','f','g','h','i','j'};
        char List[ListLength]={'a','b','c'};
        Perm(List, 0, ListLength-1);
        system("pause");
        return 0;

    }

    2. 求集合所有子集的算法实现:

    /*
      Name:
      Copyright:
      Author: XuLei
      Date: 01-11-05 11:34
      Description: 求一个集合(List)的所有子集,并输出
      Algorithms: 由SubSet函数来求所有的子集,SubSet(char *List, int m, char *Buffer, int flag)
                  基本思想为首先取出List[m],然后依次把List[m+1...ListLength-1]加到List[m]后面,
                  每加一个,存储在集合Buffer[]中,并输出。由flag标识数组Buffer的长度。
                  以集合{a,b,c}为例,首先取出a存入Buffer[0],输出。
                                     然后调用SubSet(char *List, 1, char *Buffer, 1)把Buffer[1]=b
                                        输出ab。
                                     再调用SubSet(char *List, 2, char *Buffer, 2) 把Buffer[2]=c
                                        输出abc。
                                     再进入SubSet(char *List, 1, char *Buffer, 1) 把Buffer[1]=c
                                        输出ac。
                                     退回最外层的循环。
                                     取出b存入Buffer[0],输出。
                                     然后调用SubSet(char *List, 1, char *Buffer, 1)把Buffer[1]=c
                                        输出bc。
                                     取出c存入Buffer[0],输出。              
    */
    #include <iostream>
    using namespace std;
    const int ListLength=10;
    //const int ListLength=3;

    //输出Buffer集合
    void Output(char *Buffer, int flag)
    {
         static int count=1;
         if(count==1)
         {
                  cout<<count++<<": { }"<<endl;       
         }
         cout<<count++<<": {";
         for(int i=0; i<=flag; i++)
         {
                  cout<<Buffer[i];           
         }
         cout<<"}"<<endl;
    }
    //找到元素c在集合List中的位置
    int Index(char *List, char c)
    {
         for(int i=0; i<=ListLength-1; i++)
         {
                  if(c==List[i])
                  {
                        return i;           
                        break;
                  }                
         }
         return -1;   
    }

    void SubSet(char *List, int m, char *Buffer, int flag)
    {   
         if(m <= ListLength-1)
         {
              /*if(m==0)
              {
                      Buffer[0]=List[0];
              }*/
              //Buffer[flag]=List[m];
              /*if(flag==0)
              {
                    Buffer[flag]=List[m];
              }*/
            
              for(int i=(flag==0) ? 0 : Index(List,Buffer[flag-1])+1; i<=ListLength-1; i++)
              //当flag==0时,Buffer中没有任何元素,此时i=[0...ListLength-1]
              //当flag>0时,找到Buffer中的最后一个元素在集合List中的位置i,把[i....ListLength-1]
              //处的元素,加到Buffer元素的最后面
              {
                    Buffer[flag]=List[i];              
                    Output(Buffer,flag);
                    SubSet(List, m+1, Buffer,flag+1);
              }        
         }
         return;
    }

    int main()
    {
        char List[ListLength]={'a','b','c','d','e','f','g','h','i','j'}; 
        //char List[ListLength]={'a','b','c'};
        char Buffer[ListLength]={' ',' ',' ',' ',' ',' ',' ',' ',' ',' '};
        //char Buffer[ListLength]={' ',' ',' '};
        //int flag=0;
        //TEST
        //cout<<Index(List,'c');  OK
        SubSet(List,0,Buffer,0);
        system("pause");
        return 0; 
    }

    ///

    参考:

    排列组合算法:http://blog.csdn.net/todototry/article/details/1403807


    展开全文
  • 加法原理和乘法原理,是排列组合中的二条基本原理,在解决计数问题中经常运用。掌握这两条原理,并能正确区分他们,至关重要。 加法原理 若完成一件事情3类方式,其中第一类方式1种方法,第二类方式3种方法...

    加法原理和乘法原理,是排列组合中的二条基本原理,在解决计数问题中经常运用。掌握这两条原理,并能正确区分他们,至关重要。

    加法原理

    若完成一件事情有3类方式,其中第一类方式有1种方法,第二类方式有3种方法,第三类有2种方法,这些方法都不相同,但任选一种方法都可以完成此事,则完成这件事情共有1+3+2=6种方法,这一原理称为加法原理。
    例如:从甲地到乙地有三类方式,一是汽车,二是火车,三是飞机。若一天中汽车有2班,火车有4班,飞机有一班,那么从甲地到乙地共有多少种不同的走法。共有2+4+1=7种。

    乘法原理

    若完成一件事情分r个步骤,其中第一个步骤有m1种方法,第二个步骤有m2种方法……第步骤共有mr种方法,各步骤连续或同时完成,这件事才算完成,则完成这件事共有m1*m2*……*mr种方法。
    例如:从甲地到丙地必须经过乙地。从甲地到乙地有4条路线,从乙地到丙地有3条路线,问从甲地到丙地共有多少种不同的走法?
    解:要从甲地到达丙地,必须经过两个步骤:先从甲地到乙地,有4条路线;再从乙地到丙地,有3条路线。只有这两个步骤都完成了,才能完成这种事情,缺少哪一个步骤都不行。因此从甲地到丙地共有4*3=12种走法。

    加法原理和乘法原理的区别

    以上两个基本原理在排列组合问题中将会反复使用。这两个原理回答的都是关于完成一件事情的不同方法的种数问题,但是又有根本区别。加法原理针对的是“分类”问题,若完成一件事情有多类方式,每一类方式的各种方法相互独立,用其中任何一种方法都可以完成这件事情,则用加法原理;而乘法原理针对的是“分步”问题,若完成一件事情必须依次经过多个步骤,每一个步骤的各种方法相互依存,只有各种步骤都完成才算做完成这种事情,则这时用乘法原理

    排列数公式推理过程

    例:用1、2、3这3个数字可以组成多少个数字十位和个位不重复的两位数?
    解:要组成数字不重复的两位数,需要经过两个步骤:第一步确定十位上的数,数字1、2、3都可以放在十位上,共有3种方法;第二步确定个位上的数,因为要求个位数与十位数不能重复,所以个位上的数,只能从三个数字中去掉十位数后所剩的两个数字中任选一个,共有2种方法。只有十位和个位上的数都确定了,才能组成数字不重复的两位数,这两个步骤缺少哪一个都不行。因此,根据乘法原理,3*2=6.

    上例中,我们把数字1、2、3称为元素。组成数字不重复的两位数这个问题,从3个不同的元素中任取2个,然后按顺序排成一列数,由于这样的排列与数字不重复的两位数是一一对应的,因此求数字不重复的两位数的个数等同于求这样的排列个数。

    推理过程:从n个不同元素中取出m个不同元素排成一列,必须经过m个步骤。
    第一步,确定第1个位置上的元素,可以从这n个元素中任取1个放在这个位置上,共有n种方法,即n-(1-1)括号内为位置数减1;
    第二步,确定第2个位置上的元素,可以从剩下的n-1个元素中任取1个放在这个位置上,共有n-1种方法,即n-(2-1);
    ……
    第m步,确定第m位置上的元素,第m位置上的元素从剩下的n-(m-1)个元素中任选一个,共有n-m+1种方法。根据乘法原理,全部确定这m个位置的元素共有n(n-1)(n-2)……*(n-m+1)种方法。由于一种方法对应一个排列,所以所有这样排列的个数即排列数。

    不可重复排列数公式.png

    组合

    排列是一个与次序有关的概念,如12,21这两个数字是两个不同的排列,但是在组合里,12和21是一个意思,因为12和21都是由1和2组合而成的,所以顺序并不会影响对组合的判断,因此,组合是与排列概念不同的问题。

    从n个不同的元素中,每次取出m个(m<=n)不同元素,不考虑顺序组成一组,叫做从n个元素中每次取出m个元素的组合。这样得出的组合个数称为组合数,记作C (n,m)

    求从n个不同元素中取出m个元素的排列数A(n,m),可以按以下两个步骤进行:
    第一步,求出这n个不同元素中取出m个元素的组合数C (n,m),
    第二步,求出每一个组合中m个元素的全排列数A(m,m),根据乘法原理得出,A(n,m)=C (n,m)*A(m,m),

    不可重复组合公式:C (n,m)=A(n,m)/A(m,m)=n!/m!(n-m)!,
    可重复组合公式:C (n,m)=(m+n-1)!/(m!(n-1)!)
    对于实际问题,必须正确判别是排列问题还是组合问题,其区别的关键在于要不要将所取出的元素进行排队。若要排队,则是排列问题,若不要排队,则是组合问题。
    以下为组合数计算器python代码。
    #!/usr/bin/env python3
    # -
    - coding: utf-8 -*-

    import math
    from tkinter import *
    class Window:
        def __init__(self, title='组合数计算器', width=300, height=120, staFunc=bool, stoFunc=bool):
            self.w = width
            self.h = height
            self.stat = True
            self.staFunc = staFunc
            self.stoFunc = stoFunc
            self.staIco = None
            self.stoIco = None
    
            self.root = Tk(className=title)
    
        def drawCenter(self):
            ws = self.root.winfo_screenwidth()#用户屏幕宽度
            hs = self.root.winfo_screenheight()#用户屏幕高度
            x = int( (ws/2) - (self.w/2) )#距屏幕左边框的像素点数
            y = int( (hs/2) - (self.h/2) )#距屏幕上边框的像素点数
            self.root.geometry('{}x{}+{}+{}'.format(self.w, self.h, x, y))
        
        def createWidgets(self):
            Label(self.root, text="所有元素数n:").grid(row=0,sticky=E)
            Label(self.root, text="取出的元素数m:").grid(row=1,sticky=E)
            Label(self.root, text="不可重复组合数:").grid(row=2,sticky=E)
            Label(self.root, text="可重复组合数:").grid(row=3,sticky=E)
            self.e1 = Entry(self.root)
            self.m = StringVar()
            self.e2 = Entry(self.root,textvariable=self.m)
            self.a1 = StringVar()
            self.e3 = Entry(self.root,textvariable=self.a1)
            self.a2 = StringVar()
            self.e4 = Entry(self.root,textvariable=self.a2)
            self.e1.grid(row=0, column=1)
            self.e2.grid(row=1, column=1)
            self.e3.grid(row=2, column=1)
            self.e4.grid(row=3, column=1)
            self.btnSer = Button(self.root, command=self.click, width=3, height=1,text='运行')
            self.btnSer.grid(row=4,column=1,sticky=E)
            btnQuit = Button(self.root, text='关闭窗口', command=self.root.quit, width=8, height=1)
            btnQuit.grid(row=4,column=2)
    
        def click(self):
            n=int(self.e1.get())
            m =int(self.e2.get())
            #组合数
            a1=math.factorial(n)/math.factorial(m)/math.factorial(n-m)
            self.a1.set(int(a1))
            #不可重复组合数
            a2=math.factorial(n+m-1)/(math.factorial(m)*math.factorial(n-1))
            self.a2.set(int(a2))
            
        def loop(self):
            self.root.resizable(False, False)   #禁止修改窗口大小
            self.createWidgets()
            self.drawCenter()                       #窗口居中
            self.root.mainloop()
    
    if __name__ == '__main__':
        w = Window(width=350, height=150)
        w.loop()
    

    有5个数字,取两个数字进行组合的计算结果。

    组合数计算器.png



    作者:勇赴
    链接:https://www.jianshu.com/p/82dcdf423aa1
    來源:简书
    简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。

    展开全文
  • 排列组合公式

    千次阅读 2019-07-02 18:44:38
    注:排列与元素的顺序有关,组合顺序无关.如231与213是两个排列,2+3+1的和与2+1+3的和是一个组合. 1.排列及计算公式 从n个不同元素中,任取m(m≤n)个元素按照一定的顺序排成一列,叫做从n个不同...
  • C++实现排列组合问题

    千次阅读 2019-08-11 17:42:34
    排列组合问题是高中数学知识,但是在现实中非常需要;对于计算机编程领域来说更是数不胜数。 一、排列问题 排列(英语:Permutation)是将相异对象或符号根据确定的顺序重排,每个顺序都称作一个排列。 1.1排列数的...
  • 排列组合详解

    万次阅读 多人点赞 2018-06-11 15:46:39
    排列组合问题 排列和组合问题,其实是两种问题,区分它们的原则是 是否需要考虑顺序的不同 。排列问题, 考虑 顺序;组合问题, 不考虑 顺序。以下4个问题,哪个是排列,哪个是组合? Q1: 一套书共有1-6 ...
  • c语言实现排列组合

    千次阅读 2017-03-17 18:48:06
    排列组合是算法常用的基本工具,如何在c语言中实现排列组合呢?思路如下: 首先看递归实现,由于递归将问题逐级分解,因此相对比较容易理解,但是需要消耗大量的栈空间,如果线程栈空间不够,那么就运行不下去了...
  • 排列组合算法

    千次阅读 2014-03-03 00:34:53
    排列组合算法 排列算法: 排列算法采用递归思想很简单。如1,2,3,4我们求其排列。 首先遍历1,2,3,4. 遍历1,剩下2,3,4递归处理 遍历2,剩下1,3,4递归处理 遍历3,剩下1,2,4递归处理 遍历4,剩下1,2,3递归...
  • matlab排列组合

    千次阅读 2015-12-08 10:26:26
    matlab做排列组合:比如要ABCD的全排列(permutation),可以用perms函数  perms(['ABC']) 运行结果  CBA  CAB  BCA  BAC  ABC  ACB   >> perms([1 2 3]) ans =  3 2 1   3 1 2...
  • 排列组合的 python 实现

    千次阅读 2018-10-08 20:03:12
    排列组合是数学中很基本的知识点。所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。 排列:从n个不同元素中任取m(m≤n)个元素...
  • 排列组合公式/排列组合计算公式

    千次阅读 2014-01-23 17:29:12
    公式P是指排列,从N个元素取R个进行排列。 公式C是指组合,从N个元素取R个,不进行排列。 N-元素的总个数 R参与选择的元素个数 !-阶乘 ,如  ...即对排列顺序有要求的,既属于“排列P”计算范畴。   上问题
  • 排列顺序,组合不分 例如 把5本不同的书分给3个人,几种分法. "排列" 把5本书分给3个人,几种分法 "组合" 1.排列及计算公式 从n个不同元素中,任取m(m≤n)个元素按照一定的顺序排成一列,叫做从n个不同元素...
  • 秒杀排列组合(上)————排列篇

    万次阅读 多人点赞 2012-12-23 16:36:42
    并且排列组合问题在求职的笔试,面试出现的概率特别高,而我在网上又没有搜到比较全面题型的文章;同时,我觉得编写排列组合程序对学习递归也是很帮助的;当然,最重要的原因是排列组合本身就很有趣!所以就总结下...
  • Java实现排列组合

    千次阅读 2018-09-03 20:17:37
    在介绍排列组合前首先要介绍阶乘,因为很多排列组合的运算都是要用上阶乘。阶乘的定义如下:一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积,并且0的阶乘为1。自然数n的阶乘写作n!。 即n!=1×2×3...
  • java实现排列组合

    千次阅读 2019-03-24 16:52:42
    参考https://blog.csdn.net/qq_34937383/article/details/77647963,测试... 排列公式 组合公式 1. 计算n! = n * (n-1) * ...*2 *1 /** * 计算n的阶乘 * * @param n * @return 返回 n! */ private stat...
  • JavaScript 排列组合精髓算法

    千次阅读 2013-10-13 10:53:57
    想实现在”一堆“数据中筛选出制定的个数作为一组,就需要用排列组合,组合中没有重复的组合,排列中重复的组合(顺序不一样): //组合 function C(arr, num){  var r=[];  (function f(t,a,n){  if (n==0) ...
  • 秒杀排列组合(下)————组合篇

    万次阅读 多人点赞 2012-12-26 11:48:14
    并且排列组合问题在求职的笔试,面试出现的概率特别高,而我在网上又没有搜到比较全面题型的文章;同时,我觉得编写排列组合程序对学习递归也是很帮助的;当然,最重要的原因是排列组合本身就很有趣!所以就总结下...
  • 排列组合 dfs

    千次阅读 2013-08-03 10:48:42
    组合数 时间限制:3000 ms | 内存限制:65535 KB 难度:3 ...描述找出从自然数1、2、......特定顺序:每一个组合中的值从大到小排列组合之间按逆字典序排列。 样例输入 5 3 样例输出 543 542 541
  • 排列组合区别

    千次阅读 2017-09-05 20:24:32
    这是两个非常容易混淆的概念: 排列:从n个不同的元素中,取r个不重复的元素,按次序排列,称为从n个中取r个的无重复排列话说: 要考虑到顺序的问题,就是排列问题...话说:没有也不需要考虑顺序问题就是...
  • C++之——实现排列组合

    千次阅读 2018-11-20 17:28:14
    当涉足算法领域,排列组合应该是最基础的。最近遇到了,作个记录,小白看看,大神绕路 一、补充公式 排列的定义:从n个不同元素中,任取m(m≤n,m与n均为自然数,下同)个元素按照一定的顺序排成一列,叫做从n个不同...
  • python实现排列组合

    千次阅读 2019-10-11 15:17:56
    //其中"O"两种可能性:“S”或者“-”,罗列出所有的可能结果,且原有的顺序不能改变。 如果用其他语言实现相对比较麻烦,用python自带的迭代器就非常简单。 实现 from itertools import product arr = ["S","O",...
  • C++实现排列组合

    万次阅读 2013-04-10 23:18:56
    很多地方都遇过排列组合,比如计算问题的规模,数据的大小,占用磁盘空间多少等。 原理部分借鉴网上一篇文章,道理已经说的很清楚就不重复了。 (1) 全排列: 全排列表示把集合中元素的所有按照一定的顺序排列起来...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 122,896
精华内容 49,158
关键字:

如何判断排列组合有没有顺序