排列组合 订阅
排列组合是组合学最基本的概念。所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。 排列组合与古典概率论关系密切。 展开全文
排列组合是组合学最基本的概念。所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。 排列组合与古典概率论关系密切。
信息
外文名
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.)提出的拟阵论以及人们称之为组合几何的发展都起到了核心的推动作用。应该特别提到的是在这一时期,随着电子技术和计算机科学的发展愈来愈显示出组合学的潜在力量。同时,也为组合学的发展提出了许多新的研究课题。例如,以大规模和超大规模集成电路设计为中心的计算机辅助设计提出了层出不穷的问题。其中一些问题的研究与发展正在形成一种新的几何,人们称之为组合计算几何。关于算法复杂性的究,自1971年库克(Cook,S.A.)提出NP完全性理论以来,已经将这一思想渗透到组合学的各个分支以至数学和计算机科学中的一些分支。近20年来,用组合学中的方法已经解决了一些即使在整个数学领域也是具有挑战性的难题。例如,范·德·瓦尔登(Van der Waerden,B.L.)于1926年提出的关于双随机矩阵积和式猜想的证明;希伍德(Heawood,P.J.)于1890年提出的曲面地图着色猜想的解决;著名的四色定理的计算机验证和扭结问题的新组合不变量发现等。在数学中已经或正在形成着诸如组合拓扑、组合几何、组合数论、组合矩阵论、组合群论等与组合学密切相关的交叉学科。此外,组合学也正在渗透到其他自然科学以及社会科学的各个方面,例如,物理学、力学、化学、生物学、遗传学、心理学以及经济学、管理学甚至政治学等。根据组合学研究与发展的现状,它可以分为如下五个分支:经典组合学、组合设计、组合序、图与超图和组合多面形与最优化.由于组合学所涉及的范围触及到几乎所有数学分支,也许和数学本身一样不大可能建立一种统一的理论.然而,如何在上述的五个分支的基础上建立一些统一的理论,或者从组合学中独立出来形成数学的一些新分支将是对21世纪数学家们提出的一个新的挑战。  在中国当代的数学家中,较早地在组合学中的不同方面作出过贡献的有 华罗庚、 吴文俊、 柯召、 万哲先、 张里千和 陆家羲等.其中,万哲先和他领导的研究组在有限几何方面的系统工作不仅对于组合设计而且对于图的对称性的研究都有影响.陆家羲的有关不交斯坦纳三元系大集的一系列的文章不仅解决了组合设计方面的一个难题,而且他所创立的方法对于其后的研究者也产生了和正产生着积极的作用。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)表示。这些符号也一直用到现代。此外,在八卦中,亦运用到了排列组合。
收起全文
精华内容
下载资源
问答
  • 排列组合

    2016-03-25 20:19:48
    排列组合是组合学最基本的概念。所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。排列组合的中心问题是研究给定要求的排列和组合...

    排列组合是组合学最基本的概念。所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与古典概率论关系密切,是进一步学习的基础。

      (一)两个基本原理是排列和组合的基础

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

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

      这里要注意区分两个原理,要做一件事,完成它若是有n类办法,是分类问题,第一类中的方法都是独立的,因此用加法原理;做一件事,需要分n个步骤,步与步之间是连续的,只有将分成的若干个互相联系的步骤,依次相继完成,这件事才算完成,因此用乘法原理。

      这样完成一件事的分“类”和“步”是有本质区别的,因此也将两个原理区分开来。

      (二)排列和排列数

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

      从排列的意义可知,如果两个排列相同,不仅这两个排列的元素必须完全相同,而且排列的顺序必须完全相同,这就告诉了我们如何判断两个排列是否相同的方法。

      (2)排列数公式:从n个不同元素中取出m(m≤n)个元素的所有排列

      当m=n时,为全排列Pnn=n(n-1)(n-1)…3·2·1=n!

      (三)组合和组合数

      (1)组合:从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从 n个不同元素中取出m个元素的一个组合。

      从组合的定义知,如果两个组合中的元素完全相同,不管元素的顺序如何,都是相同的组合;只有当两个组合中的元素不完全相同时,才是不同的组合。

      (2)组合数:从n个不同元素中取出m(m≤n)个元素的所有组合的个数

      这里要注意排列和组合的区别和联系,从n个不同元素中,任取m(m≤n)个元素,“按照一定的顺序排成一列”与“不管怎样的顺序并成一组”这是有本质区别的。

      [反思] 排列与组合的共同点是从n个不同的元素中,任取m(m≤n)个元素,而不同点是排列是按照一定的顺序排成一列,组合是无论怎样的顺序并成一组,因此“有序”与“无序”是区别排列与组合的重要标志。

      简单举例:1、2、3挑两个组成一个数字和1、2、3挑两个数字是完全不一样的!1、2、3挑两个组成一个数字那是排列;1、2、3挑两个数字那是组合。例如我选1和2,排列里面12和21是两个数字!但是组合的话挑1和2就和挑2和1没有分别!!!


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

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

     

    公式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



    作者:魔法师_
    链接:https://www.jianshu.com/p/68593ea7f8f0
    来源:简书
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    展开全文
  • 排列组合 交叉组合 组合排列算法

    千次阅读 2018-06-19 11:41:31
    20180619一,交叉组合排列算法:1、前言:在项目开发的过程中负责全系统查询检索的一个模块,其中有一个查询方式叫做“交叉组合查询”,与数学中的排列组合类似,因此就开始想看一下这个该怎么写,以下为本人原创...
    20180619
    一,交叉组合排列算法:
    1、前言:
    在项目开发的过程中负责全系统查询检索的一个模块,其中有一个查询方式叫做“交叉组合查询”,与数学中的排列组合类似,因此就开始想看一下这个该怎么写,以下为本人原创文章,转载请标明出处:https://blog.csdn.net/RobinsStruggle,本人自定为java菜鸟,如有问题指出请指教,不胜感激!
    2、模型(例题):
    现有A、B、C三组球,每组数量不相同,需要在A、B、C中每组一次拿出一个球,拿出的不能与之前拿出的相等:
    A:a1、a2、a3;
    B:b1、b2;
    C:c1、c2、c3、c4;
    如果使用数学那么很快就可以得出结论,如果通过简单代码去实现这一步骤的话那么可用的代码为:
    public static void main(String[] args) {
    List<String> dataList4A = new ArrayList<String>();
    dataList4A.add("a1");
    dataList4A.add("a2");
    dataList4A.add("a3");

    List<String> dataList4B = new ArrayList<String>();
    dataList4B.add("b1");
    dataList4B.add("b2");

    List<String> dataList4C = new ArrayList<String>();
    dataList4C.add("c1");
    dataList4C.add("c2");
    dataList4C.add("c3");
    dataList4C.add("c4");

    for (String dataSon4A : dataList4A) {
    for (String dataSon4B : dataList4B) {
    for (String dataSon4C : dataList4C) {
    System.out.println(dataSon4A + dataSon4B + dataSon4C);
    }
    }
    }
    }
    3、扩展:
    上面的代码或者思维大概能够满足日常开发需求了,当时该想法还是不符合系统要求,因为系统查询条件的组数也就是说上个例子中球的组数是不确定的,那么如果使用上述的方法去实现的话似乎不太可能,而且极度不灵活,那么能不能开发一个工具类去进行根据传入的组数以及组数据去进行交叉排列组合呢?
    刚开始的时候我也是顺着前面所述的思路进行思考的,后来发现可行性不大,所以就开始慢慢摸索这个交叉排列组合的可编程化的规则,于是通过整理发现了一个规则,此处献上我的草稿:

    于是通过代码实现,并且封装成了工具类,就有了以下的代码:
    排列算法实体类:CombinationEntity.java

    排列算法操作类:CombinationPeration.java


    该两个算法文件可进行下载(想赚点C币哈哈哈哈,两个C币,望谅解!):https://download.csdn.net/download/robinsstruggle/10485775
    展开全文
  • EXCEL 利用排列组合公式列出所有排列组合情况 在excel中如何实现第一列和第二列排列组合,输出到第三列 使用这个工具:http://www.excelfb.com/点击:用几列的值排列组合成一列的值 操作如下图:如果需要输出一列,...

    对于如下问题:

    EXCEL 利用排列组合公式列出所有排列组合情况
    在excel中如何实现第一列和第二列排列组合,输出到第三列

    使用这个工具:http://www.excelfb.com/ 点击: 排列组合 -->  排列组合(用指定的几列)

    操作如下图:如果需要输出一列,选择组合合成一列

    展开全文
  • 使用说明:需要各位看官理解什么是排列组合,若有不懂,及时度娘。 排列 从m个元素中选n个元素(n≤m)进行排列 元素不能重复,只考虑顺序 eg:1,2,3的排列 1,2,3 1,3,2 2,1,3 2,3,1 3,...
  • PHP 排列组合

    千次阅读 2018-05-17 13:29:29
    几个排列组合例子:【递归】 一、出处:对数组作排列组合的PHP算法 | maraboy function array_comb($array, $n) { $results = []; // case $n == 1, give straightforward result if ($n == 1) { foreach ($...
  • 排列组合公式 排列组合公式/排列组合计算公式 公式P是指排列,从N个元素取M个进行排列。 公式C是指组合,从N个元素取M个进行组合,不进行排列。 N-元素的总个数 M参与选择的元素个数 !-阶乘,如9!=9*8*...
  • 重温排列组合

    2019-01-22 14:54:10
    高中学过的排列组合到现在已经很模糊了,最近在写程序的时候,需要用到排列组合优化输出结果,拿来用的时候发现,排列组合很模糊,这个 怎么计算呢,习惯性的打开了百度 搜索一下,找一下网上的资源,看了几十分钟,...
  • 排列组合问题

    千次阅读 2018-11-25 12:24:52
    排列组合问题 ​ 排列组合是组合数学里的两大经典问题,下面我们先来看一下它的定义: ​ 排列:从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。 ​ ...
  • 排列组合计算公式简易版

    万次阅读 2018-08-30 21:15:25
    记录一下排列组合中一些重要又常用的公式。 1.0!=10!=10! = 1 2.Pmn=n(n−1)(n−2)⋯(n−m+1)=n!(n−m)!Pnm=n(n−1)(n−2)⋯(n−m+1)=n!(n−m)!P_n ^ m = n(n-1)(n-2)\cdots (n-m+1) = \frac{n!}{(n-m)!} 3.pnn=n...
  • 调用 itertools 获取排列组合的全部情况数 # -*- encoding=utf-8 -*- from itertools import combinations,permutations # 排列 test_data = {'1', '2', '3'} print('排列有:') for i,j in permutations(test_...
  • 排列组合模板

    2016-08-16 15:04:04
    排列组合数。
  • 排列组合-排列

    2014-03-28 11:09:06
    排列组合-排列
  • 排列组合讲解

    千次阅读 2015-02-07 09:56:57
    排列组合是组合学最基本的概念。所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。排列组合的中心问题是研究给定要求的排列和组合...
  • 排列组合算法

    千次阅读 2019-06-07 10:09:05
    命题:多维数组的排列组合 或 多个数组之间的排列组合 命题场景: 现在有一批手机,其中颜色有[‘白色’,‘黑色’,‘金色’];内存大小有[‘16G’,‘32G’,‘64G’],版本有[‘移动’,‘联通’,‘电信’],...
  • python实现排列组合

    2020-07-30 17:24:06
    排列组合是组合学最基本的概念。所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。 itertools参考文档: ...
  • java 实现排列组合的所有情况,是一个常用的工具,为所需要的业务逻辑提供基本的构件
  • 加法原理和乘法原理,是排列组合中的二条基本原理,在解决计数问题中经常运用。掌握这两条原理,并能正确区分他们,至关重要。 加法原理 若完成一件事情有3类方式,其中第一类方式有1种方法,第二类方式有3种方法...
  • 排列组合错排

    2017-12-17 20:35:37
    排列组合中,会遇到如下问题:  有10支相同的笔,现将笔盖与笔杆分开并且打乱,随机将笔杆与笔盖组合在一起,问有多少种情况使得没有一支笔杆与正确的笔盖组合? 这类问题称为错排问题。错排问题计算公式如下...
  • 排列组合函数

    2019-04-11 20:36:21
    对于排列组合求组合数如果直接求值数据范围太大,时间太长。 其实排列组合还是挺有规律的,例如下面的 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) 1 2 3 4 5 6 (2,2) (2,3) (2,4) (2,5) (2,6) 1 ...
  • 排列组合知识

    千次阅读 2013-11-20 13:30:31
    排列组合是组合学最基本的概念。所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。排列组合的中心问题是研究给定要求的排列和组合...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 226,932
精华内容 90,772
关键字:

排列组合