排列组合公式
排列组合公式是什么?让我们一起了解一下吧。
排列A(n,m)=n×(n-1).(n-m+1)=n!/(n-m)!(n为下标,m为上标,以下同),组合C(n,m)=P(n,m)/P(m,m)=n!/m!(n-m)!;例如A(4,2)=4!/2!=4*3=12;C(4,2)=4!/(2!*2!)=4*3/(2*1)=6。
排列组合是组合学的基本概念,排列就是指从给定个数的元素中取出指定个数的元素进行排序,组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。组合的定义有两种,定义的前提条件是m≦n。①.从n个不同元素中,任取m个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合。②.从n个不同元素中,取出m个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数。
今天的分享就是这些,希望能帮助到大家。
排列组合公式 Cn An
递推递归与排列组合
说明排列组合
排列组合问题在暴力枚举的情况一般有3种情况
我们在此记个数为N
- 情况一:打印n个数的全排列:
N=n!N=n!
- 情况二:打印n个数中任意m个数的全排列
N=Amn=n!(n−m)!N=Anm=n!(n−m)!
- 情况三:打印n个数中任意m个数的组合
N=Cmn=n!m!(n−m)!N=Cnm=n!m!(n−m)!
递推与递归递推是按照一定的规律来计算序列中的每个项,通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复,该算法利用了计算机速度快和不知疲倦的机器特点。
所谓递归,实际上是一种把大问题逐步缩小成最小同类问题的过程,其中最小问题的解是已知的,往往是所给条件。
比较两者,可清楚地发现递归是逆向的递推。递推是从最小问题出发一步步向前求解,递归则是从最大问题开始不断去调用自己达到最小问题的解然后再逐层归来。
所以一般来讲递推的效率大于递归,并且在递归中问题的n是在计算前就已经知道的,而递推可以在求解中确定。
我们以斐波那契数列距离,其数学递推公式如下(无论递推还是递归,一般都从递推公式开始分析)
⎧⎩⎨f(n)=f(n−1) f(n−2)f(1)=f(2)=1n>2,n∈N {f(n)=f(n−1) f(n−2)f(1)=f(2)=1n>2,n∈N
接下来我们利用代码来分别示范一遍两种方法
- 斐波那契——递归
#include
- 斐波那契——递推
#include
算法
我们对上述排列组合对三种情况写代码
情况一输出全排列
STL方法:
#include
递归方法:
#include
情况二
想要打印n个数中任意m个数的全排列其实很简单,只需要在上述代码中稍作修改即可
打印序列函数printSequence
void printSequence(vector
获取全排列的函数Perm(增加了计数功能,需传入变量cnt)
/* *这里num必须用引用。 *否则迭代器指向的num是原实例,而传入的num是拷贝的实例,输出结果都是原序列。 *详细情况可以调用下方的test尝试下(该函数已被注释) *参数:num:原序列,begin:vector的begin迭代器, end:vector的end迭代器,m:从n个数中打印m个数的全排列中的m,cnt:用于统计最后全排列个数 */void Perm(vector
情况三
组合不同于排列,排列有序而组合无序。所以,我们先来研究其子集的生成。
我们按如下记集合A,其中n为其元素的个数
A={x0,x1,x2,...,xn−1}A={x0,x1,x2,...,xn−1}
其子集有
ϕ,{x0},{x1},...,{x0,x1,...,xn−1}ϕ,{x0},{x1},...,{x0,x1,...,xn−1}
不妨设子集个数为N,则有
N=2nN=2n
这个式子很容易跟二进制联系起来,我们不由得会去想子集跟二进制之间的关系
我们不妨构造一个n位的二进制数,每一位都对应集合中的一个元素,当子集中包含该元素,则对应的二进制数的该位上的值就为1否则为0,那么每个子集都对应一个独一无二的n位二进制数了。
以n=3时的集合为例,此时有
A={x0,x1,x2}A={x0,x1,x2}
则其子集与二进制数对应关系如下
子集 |
空集 |
x0 |
x1 |
x0,x1 |
x2 |
x2,x0 |
x2,x1 |
x2,x1,x0 |
二进制数 |
000 |
001 |
010 |
011 |
100 |
101 |
110 |
111 |
此外我们还需要知道:
- 位运算
1<
- 与运算
10001&101=10001&00101=0000110001&101=10001&00101=00001
此处与运算仅举例,当两个二进制数位数不一致则再前面补0然后对应位置做与运算
接下来我们以打印集合{0,1,2,..,n-1}的子集为例,则有如下函数
void print_subset(int n){ for (int i = 0; i < (1 << n); i ) //从000到2^n-1对应的二进制,一共2^n个子集 { //将每个子集都取出,对应数字i //在子集i的情况下,不断尝试取元素个数为j,其中每个元素的值跟其序号相同都为j for (int j = 0; j < n; j ) //如果子集i中含多个数,此处的for则打印多个数,若i仅1个数此处for也只寻找并打印仅含的这一个数j if (i & (1 << j)) //将2的j次幂转化为二进制形式,通过与运算,去测试仅包含一个十进制数j的集合是不是该子集的子集 cout << j << " "; //如果是,则说明子集i中包含十进制数j,此时打印j。 cout << endl; }}
那么基础知识已经介绍完了,我们回到情况三,对照子集对应二进制数的方法。我们知道一个子集对应唯一的一个二进制数,那么一个有k个元素的子集它对应二进制数一定有k个1。所以找查子集的问题就变成了找查含k个1的二进制数。
这里介绍个技巧(kk为一个名为kk的二进制数)
kk = kk & (kk-1)
它可以跳过0消除数中最后一个1,这样我们执行此操作的次数就是二进制数中含1的个数
则针对情况三有如下代码
//打印n个数中取m个数的组合void print_set(int n, int m){ for (int i = 0; i < (1 << n); i ) { int cnt = 0, kk = i; while (kk) { kk = kk & (kk - 1); cnt ; } if (cnt == m) { for (int j = 0; j < n; j ) //此处跟上方print_subset函数同理 if (i & (1 << j)) cout << j << " "; cout << endl; } }}
参考
- 罗永军,郭卫斌. 算法竞赛入门到进阶[M]. 北京 : 清华大学出版社,2019.
- 07-06生活
中秋节传统活动
- 05-09生活
晚上睡觉带耳塞对耳朵有害吗
- 04-26生活
食品保质期长好还是短好
- 11-14生活
梦见自己怀了个男孩
- 03-05生活
寒食节的由来
- 08-06科技
文档结构图怎么做
- 03-30生活
干的红辣椒放久了还能吃吗
- 05-08生活
棕色皮鞋上的黑色污渍怎么去除
推荐
- 12022文员辞职报告范文366
- 2火车60号座位在什么位置233
- 3史莱姆容易断怎么补救137
- 4如何修改Zend Studio的语言环境为中文101
- 5物理九年级上册知识点322
- 6鼠宝宝成语起名女孩名字203