1. 定义:
组合数:从m个不同元素中任取n(n<=m)个元素拼成一组,叫做从m中取n个元素的组合。能够取的所有可能叫组合数。公式如下:
全排列:从m个不同元素中,任取n(n<=m)个元素按照一定顺序排列起来,叫做从m中取n个数的一个排列。当m=n时的所有排列情况,叫做全排列。
全排列数f(n) = n!
区别:排列可以看作是同样情况下组合的子集,由于需要按顺序排列,因此少了一些情况。
2. JAVA实现
-->全组合:
运行结果:
运行过程:
举例3个元素:a,b,c。所以一共有2^3=8个结果。所以i=0,1,2,3,...,7分别对应输出以上结果
将i转换为二进制i=1=001,i=2=010,i=3=011
1)j=0;1<<j =001与i=001相与返回1 输出a
-->全排列:
递归
* 从集合中依次选出每一个元素,作为排列的第一个元素,然后对剩余的元素进行全排列,如此递归处理
* 从而得到所有元素的全排列。以对字符串abc进行全排列为例,我们可以这么做:以abc为例:
* 固定a,求后面bc的排列:abc,acb,求好后,a和b交换,得到bac
* 固定b,求后面ac的排列:bac,bca,求好后,c放到第一位置,得到cba
* 固定c,求后面ba的排列:cba,cab。
** 即递归树:
str: a b c
ab ac ba bc ca cb
result: abc acb bac bca cab cba
运行结果: