1、我们知道,排列个数的计算公式如下:
组合个数的计算公式如下:
那么,计算排列或组合的数量,通过上面的公式就很容易就算出来了,其Java的实现如下:
/**
* 计算阶乘数,即n! = n * (n-1) * ... * 2 * 1
* @param n
* @return
*/
private static long factorial(int n) {
return (n > 1) ? n * factorial(n - 1) : 1;
}
/**
* 计算排列数,即A(n, m) = n!/(n-m)!
* @param n
* @param m
* @return
*/
public static long arrangement(int n, int m) {
return (n >= m) ? factorial(n) / factorial(n - m) : 0;
}
/**
* 计算组合数,即C(n, m) = n!/((n-m)! * m!)
* @param n
* @param m
* @return
*/
public static long combination(int n, int m) {
return (n >= m) ? factorial(n) / factorial(n - m) / factorial(m) : 0;
}
2、有时候,我们不仅需要知道排列或组合的数量,而且需要知道有哪些排列或组合,并列举出所有的排列或组合,人工列举工作量大而且容易出错,那么,如何利用计算机帮忙列举出所有的这些排列或组合呢?
(1)排列
采用递归即可枚举出所有的排列情况,相关Java实现如下:
/**
* 排列选择(从列表中选择n个排列)
* @param dataList 待选列表
* @param n 选择个数
*/
public static void arrangementSelect(String[] dataList, int n) {
System.out.println(String.format("A(%d, %d) = %d", dataList.length, n, arrangement(dataList.length, n)));
arrangementSelect(dataList, new String[n], 0);
}
/**
* 排列选择
* @param dataList 待选列表
* @param resultList 前面(resultIndex-1)个的排列结果
* @param resultIndex 选择索引,从0开始
*/
private static void arrangementSelect(String[] dataList, String[] resultList, int resultIndex) {
int resultLen = resultList.length;
if (resultIndex >= resultLen) { // 全部选择完时,输出排列结果
System.out.println(Arrays.asList(resultList));
return;
}
// 递归选择下一个
for (int i = 0; i < dataList.length; i++) {
// 判断待选项是否存在于排列结果中
boolean exists = false;
for (int j = 0; j < resultIndex; j++) {
if (dataList[i].equals(resultList[j])) {
exists = true;
break;
}
}
if (!exists) { // 排列结果不存在该项,才可选择
resultList[resultIndex] = dataList[i];
arrangementSelect(dataList, resultList, resultIndex + 1);
}
}
}
(2)组合
采用递归即可枚举出所有的排列情况,相关Java实现如下:
/**
* 组合选择(从列表中选择n个组合)
* @param dataList 待选列表
* @param n 选择个数
*/
public static void combinationSelect(String[] dataList, int n) {
System.out.println(String.format("C(%d, %d) = %d", dataList.length, n, combination(dataList.length, n)));
combinationSelect(dataList, 0, new String[n], 0);
}
/**
* 组合选择
* @param dataList 待选列表
* @param dataIndex 待选开始索引
* @param resultList 前面(resultIndex-1)个的组合结果
* @param resultIndex 选择索引,从0开始
*/
private static void combinationSelect(String[] dataList, int dataIndex, String[] resultList, int resultIndex) {
int resultLen = resultList.length;
int resultCount = resultIndex + 1;
if (resultCount > resultLen) { // 全部选择完时,输出组合结果
System.out.println(Arrays.asList(resultList));
return;
}
// 递归选择下一个
for (int i = dataIndex; i < dataList.length + resultCount - resultLen; i++) {
resultList[resultIndex] = dataList[i];
combinationSelect(dataList, i + 1, resultList, resultIndex + 1);
}
}
3、测试
(1)完整的测试代码如下
/**
* 从n个数里取出m个数的排列或组合算法实现
* @author chengesheng
* @date 2016年9月28日 下午3:18:34
*/
import java.util.Arrays;
public class MathTest {
public static void main(String[] args) {
arrangementSelect(new String[] {
"1", "2", "3", "4"
}, 2);
combinationSelect(new String[] {
"1", "2", "3", "4", "5"
}, 3);
}
/**
* 排列选择(从列表中选择n个排列)
* @param dataList 待选列表
* @param n 选择个数
*/
public static void arrangementSelect(String[] dataList, int n) {
System.out.println(String.format("A(%d, %d) = %d", dataList.length, n, arrangement(dataList.length, n)));
arrangementSelect(dataList, new String[n], 0);
}
/**
* 排列选择
* @param dataList 待选列表
* @param resultList 前面(resultIndex-1)个的排列结果
* @param resultIndex 选择索引,从0开始
*/
private static void arrangementSelect(String[] dataList, String[] resultList, int resultIndex) {
int resultLen = resultList.length;
if (resultIndex >= resultLen) { // 全部选择完时,输出排列结果
System.out.println(Arrays.asList(resultList));
return;
}
// 递归选择下一个
for (int i = 0; i < dataList.length; i++) {
// 判断待选项是否存在于排列结果中
boolean exists = false;
for (int j = 0; j < resultIndex; j++) {
if (dataList[i].equals(resultList[j])) {
exists = true;
break;
}
}
if (!exists) { // 排列结果不存在该项,才可选择
resultList[resultIndex] = dataList[i];
arrangementSelect(dataList, resultList, resultIndex + 1);
}
}
}
/**
* 组合选择(从列表中选择n个组合)
* @param dataList 待选列表
* @param n 选择个数
*/
public static void combinationSelect(String[] dataList, int n) {
System.out.println(String.format("C(%d, %d) = %d", dataList.length, n, combination(dataList.length, n)));
combinationSelect(dataList, 0, new String[n], 0);
}
/**
* 组合选择
* @param dataList 待选列表
* @param dataIndex 待选开始索引
* @param resultList 前面(resultIndex-1)个的组合结果
* @param resultIndex 选择索引,从0开始
*/
private static void combinationSelect(String[] dataList, int dataIndex, String[] resultList, int resultIndex) {
int resultLen = resultList.length;
int resultCount = resultIndex + 1;
if (resultCount > resultLen) { // 全部选择完时,输出组合结果
System.out.println(Arrays.asList(resultList));
return;
}
// 递归选择下一个
for (int i = dataIndex; i < dataList.length + resultCount - resultLen; i++) {
resultList[resultIndex] = dataList[i];
combinationSelect(dataList, i + 1, resultList, resultIndex + 1);
}
}
/**
* 计算阶乘数,即n! = n * (n-1) * ... * 2 * 1
* @param n
* @return
*/
public static long factorial(int n) {
return (n > 1) ? n * factorial(n - 1) : 1;
}
/**
* 计算排列数,即A(n, m) = n!/(n-m)!
* @param n
* @param m
* @return
*/
public static long arrangement(int n, int m) {
return (n >= m) ? factorial(n) / factorial(n - m) : 0;
}
/**
* 计算组合数,即C(n, m) = n!/((n-m)! * m!)
* @param n
* @param m
* @return
*/
public static long combination(int n, int m) {
return (n >= m) ? factorial(n) / factorial(n - m) / factorial(m) : 0;
}
}
(2)测试结果
A(4, 2) = 12
[1, 2]
[1, 3]
[1, 4]
[2, 1]
[2, 3]
[2, 4]
[3, 1]
[3, 2]
[3, 4]
[4, 1]
[4, 2]
[4, 3]
C(5, 3) = 10
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]
经验证,输出的结果正确,同预期结果相符。
- 大小: 1.1 KB
- 大小: 1.1 KB
分享到:
相关推荐
本资源附带文档解释了排列组合算法的实现和原理。其中排列算法是基于递归实现的,组合算法是基于高效的位移法实现的。代码是使用Java版实现的。
排列组合算法实现,支持模板类。支持重复数的排列。算法采用递归方法,简单易懂。
排列组合 排列 组合 java排列组合算法 排列组合算法
Java排列组合算法 - 郭睿的专栏 - CSDN博客Java排列组合算法 - 郭睿的专栏 - CSDN博客
Java排列组合算法
6位数,共有几种排列组合的算法,java实现
Java排列组合_组合算法,利用list及set的无序性, 通过递归实现,不同于以往的排列组合 自娱自乐
此外,文档还提供了各种排列组合算法的详细代码示例和实现细节,包括递归和迭代方法。文档还涵盖了高级主题,如如何计算有重复元素的排列组合数量,以及如何优化这些算法的性能。 无论您是Java编程的初学者还是有...
所使用的算法应该是效率最高的算法,而且这两个类都只是对需要排列组合的数组的下标进行处理,所以能对任何类型的数组进行排列组合。
介绍了几种用JAVA实现的排列组合算法,有需要的朋友可以参考一下
主要为大家详细介绍了高效的java版排列组合算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
用java语言写的组合数学中生成排列算法的代码,并由界面
实现了排列组合算法的类(JAVA),实现了排列组合算法的类(JAVA)
这是算法课老师叫我们做的一个算法作业,我是按照他说的写的,如果自己写的话完全用不着那么多行,呵呵。
阶乘与排列组合算法!在各行各业都能用得到的,比较彩票业,以及复杂的生产环境预测等软件开发
主要介绍了Java获得一个数组的指定长度排列组合算法,结合实例形式分析了java排列组合相关数组遍历、运算操作技巧,需要的朋友可以参考下
该资源为本人自己写的交叉组合算法代码的工具类,一共两个,搭配文章看效果更好!
主要介绍了Java实现字符数组全排列的方法,涉及Java针对字符数组的遍历及排序算法的实现技巧,需要的朋友可以参考下
今天 写了一个java小程序 是将a,b,c,d,e,f,g这7个字母的全排列打印出来,排除a,d相邻的情况 ...算然很简单 但是我用递归调用的方式写的 算法还是很不错的 建议新手们学习 看不懂或者有更好的想法的的请留言^_-
2016-09-24_213732.wmv ...22_排列组合(1).flv 23_排列组合(2).flv 24_概率(1).flv 25_概率(2).flv 26_队列和栈(2).flv 27_大数据(1).flv 28_大数据(2).flv 29_动态规划(1).flv 30_动态规划(2).flv