排列(Amn)与组合(Cmn)算法详解

这篇具有很好参考价值的文章主要介绍了排列(Amn)与组合(Cmn)算法详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

不区分个体差异和顺序时用Cmn(m小n大),需要区分个体和顺序时候用Amn。

例1:从10个相同的球里取出5个球,不需要区分先后顺序,也不区分其他个体特征,一把抓过去够5个就行,这就是C510(m=5,n=10)。

例2:有10把凳子,需要安排10个人去坐,问有多少种可能性。这里,就需要体现顺序。那么,坐第一个凳子有10种选择,做第二个凳子的有9种选择,以此类推,坐最后一个凳子的就只剩1种选择,每个选择之间是“和”的关系,即为10x9x8x7x6x5x4x3x2x1=A1010=10!。

下面是排列与组合的一般公式:(!代表阶乘)

 A510 = 10! ÷ 5! = 6 x 7 x  8 x 9 x 10

int A(int m, int n)
{
	int ret = 1;
	for (int i = m + 1; i <= n; i++)
		ret *= i;
	return ret;
}

C38 = (8 x 7 x 6) / (3 x 2 x 1)

cmn和amn的公式,算法,数据结构

 注意"ret = ret * (n - i + 1) / i;"不能写成"ret *= (n - i + 1) / i;" 因为(n - i + 1) / i可能是小数,会计算错误

int C(int m, int n) {
	int ret = 1;
	for (int i = 1; i <= m; i++)
		ret = ret * (n - i + 1) / i;
	return ret;
}

我们还可以用递推写法,数组记录,用空间换时间,原理就是杨辉三角形,如下图。

cmn和amn的公式,算法,数据结构

cmn和amn的公式,算法,数据结构

void init_C() {
	for (int i = 0; i < N; i++) { //N表示预处理最大的下标
		for (int j = 0; j <= i; j++) {
			if (j == 0 || j == i)//每一行最右边和最左边的数是1
				c[i][j] = 1;
			else
				c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
		}
	}
}

注意:函数写法前一个数(m)比后一个数(n)要小,递推写法数组c[m][n]的前一个数(m)比后一个数n要大。例如:函数写法C(3, 8)  =  递推写法数组c[8][3]文章来源地址https://www.toymoban.com/news/detail-757700.html

到了这里,关于排列(Amn)与组合(Cmn)算法详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 一致性总线CMN600AE-ARM系列

    主要介绍一致性总线CMN600AE,根据arm官网的spec来概述其模块。 提示:以下是本篇文章正文内容,下面案例可供参考 CMN600ae是基于Mesh拓扑结构,对外支持AMBA CHI/ACE-LITE等接口,内部改用路由结构转发数据,并提供硬件一致性和系统缓存,还支持多芯片互联。CMN600在T16FFC上可以做

    2024年02月04日
    浏览(45)
  • 【C++】 排列与组合算法详解(进阶篇)

    写在前面 我上次发了一篇题解:C++排列与组合算法详解 最开始,我是抱着水题解的想法写的,但却成为了阅读量 最高 的文章,没有之一。 所以今天咱们来重制一篇文章,介绍几个进阶优化版的算法。 算法1:朴素算法 思路 具体见 C++排列与组合算法详解 缺点 不能将结果取

    2024年02月13日
    浏览(40)
  • 青蛙跳台阶(C语言数学排列组合公式求解法)

    题目:从前有一只青蛙他想跳台阶,有n级台阶,青蛙一次可以跳1级台阶,也可以跳2级台阶;问:该青蛙跳到第n级台阶一共有多少种跳法。 当只有跳一级台阶的方法跳时,总共跳n步,共有1次跳法                                 当用了一次跳二级台阶的方法跳时,总共

    2024年02月08日
    浏览(41)
  • 算法--排列组合

    2024年02月16日
    浏览(39)
  • java实现排列组合算法

    我这里只写了组合的算法。         假设现有 M=4 个数据 a,b,c,d。从中随机抽取n个数,n为1—4个数据进行组合。那么数学中的计算组合方式为C(4,1) + C(4,2) + C(4,3) + C(4,4)  = 4 + 6 + 4 + 1 = 15。那么共有15种组合方式。 方案一:此方法容易理解但是效率慢         我的做

    2024年02月13日
    浏览(49)
  • 算法第二期——排列组合(Python)

    目录 排列函数permutations( ) 易错点 组合函数combinations( ) 手写排列和组合代码  1.暴力法/

    2023年04月18日
    浏览(36)
  • 【算法教程】排列与组合的实现

    在讲排列与组合之前,我们先定义数据元素类型Fruit 对N个不同元素进行排序,总共有多少不同的排列方式? 例子:某水果店有以下水果,请对所有水果进行全排列,请输出所有排列 排列算法的javascript实现模板(DSF,最优解in-place) 测试结果 对N个不同元素进行排序,总共有多少不

    2024年02月07日
    浏览(48)
  • 详解Python中的排列组合生成器

    在实际的开发场景中,经常需要遍历多个数组中的元素,将它们组合在一起使用。要取完所有可能的组合,最基本的方法是使用嵌套的循环,有多少个数组就嵌套多少层循环。嵌套循环是基本的原理,但不够简洁,Python中有更优雅的方式来实现这种功能。 在Python的内置模块

    2024年02月10日
    浏览(45)
  • 【算法】递归、回溯、剪枝、dfs 算法题练习(组合、排列、总和问题;C++)

    后面的练习是接着下面链接中的文章所继续的,在对后面的题练习之前,可以先将下面的的文章进行了解👇: 【算法】{画决策树 + dfs + 递归 + 回溯 + 剪枝} 解决排列、子集问题(C++) 思路 题意分析 :要求根据给出的数字,算出合法的括号组成个数。根据题目,我们可以总

    2024年02月22日
    浏览(50)
  • 【C/C++练习】经典的排列组合问题(回溯算法)——电话号码的字母组合

    📖题目描述 题目出处 :电话号码的字母组合 示例: 📖题解  这是一道典型的排列组合问题,根据输入,我们需要找到所有的组合。下面以输入字符串 digits = \\\"23\\\" 为例来讲解这道题目。 图解: 分析:  首先要知道输入的字符串 \\\"23\\\" 中的数字字符分别对应哪些字符串,其中

    2024年02月16日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包