一个从M个数字里面取N个数字的组合
没用到递归的实现,将选取的位置标记为1没选取的标记为0
返回的是数组的形式。
版本1
public class CombineUtil {
private static int[] copy(int[] bs){
int[] result = new int[bs.length];
for(int i=0;i<bs.length;i++){
result[i] = bs[i];
}
return result ;
}
public static void print(List<int[]> l){
for(int i=0;i<l.size();i++){
int[] a = (int[])l.get(i);
for(int j=0;j<a.length;j++){
System.out.print(a[j]+"\t");
}
System.out.println();
}
}
public static void print(int[] a){
for(int j=0;j<a.length;j++){
System.out.print(a[j]+"\t");
}
System.out.println();
}
/**
* 从m里选n个数字
* @param m
* @param n
* @return
*/
public static List<int[]> combineEx(int m, int n) {
if (m < n) {
return null;
}
List<int[]> list = new ArrayList<int[]>();
int[] cn = new int[m];
for (int i = 0; i < cn.length; i++) {
if (i < n) {
cn[i] = 1;
} else {
cn[i] = 0;
}
}
boolean flag = true;
do {
int pos = 0;
int sum = 0;
boolean tempFlag = true;
list.add(copy(cn));
if (m == n || m == 0) {
return list;
}
for (int i = 0; i < m - 1; i++) {
if (cn[i]==1 && cn[i+1]==0) {
cn[i]=0;
cn[i+1]=1;
pos = i;
break;
}
}
for (int i = 0; i < pos; i++) {
if (cn[i] == 1) {
sum ++;
}
}
for (int i = 0; i < pos; i++) {
if (i < sum) {
cn[i] = 1;
} else {
cn[i] = 0;
}
}
for (int i = m-n; i < cn.length; i++) {
if (cn[i] == 0) {
tempFlag = false;
break;
}
}
flag = !tempFlag;
} while (flag);
list.add(copy(cn));
return list;
}
public static void main(String[] args) {
try {
CombineUtil.print(combineEx(3, 3));
} catch (Exception e) {
e.printStackTrace();
}
}
版本二
public class CombinationEx {
private List<String> list = new ArrayList<String>();
private void mn(int m, int n) {
if ( m < n) {
throw new IllegalArgumentException("参数异常");
}
BitSet bs = new BitSet(m);
for (int i = 0; i < n; i++) {
bs.set(i, true);
}
do {
printAll(m, bs);
} while(moveNext(bs, m));
}
private void printAll(int m, BitSet bs) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < m; i++) {
if (bs.get(i)) {
sb.append("1").append(",");
} else {
sb.append("0").append(",");
}
}
sb.setLength(sb.length() - 1);
list.add(sb.toString());
}
private boolean moveNext(BitSet bs, int m) {
int start = -1;
while (start < m) {
if (bs.get(++start)) {
break;
}
}
if (start >= m) {
return false;
}
int end = start;
while (end < m) {
if (!bs.get(++end)) {
break;
}
}
if (end >= m) {
return false;
}
for (int i = 0; i < end; i++) {
bs.set(i, false);
}
for (int i = 0; i < end - start - 1; i++) {
bs.set(i);
}
bs.set(end);
return true;
}
private List<String> getList() {
return list;
}
public static void main(String[] args) {
CombinationEx co = new CombinationEx();
co.mn(5, 3);
for (int i = 0; i < co.getList().size(); i++) {
System.out.println(co.getList().get(i));
}
}
}
下面介绍全排列的算法
public class Arrange {
private int total = 0;
private ArrayList<String> arrangeList = new ArrayList<String>();
public Arrange() {
}
private void swap(String list[], int k, int i) {
String c3 = list[k];
list[k] = list[i];
list[i] = c3;
}
public void perm(String list[], int k, int m) {
if (k > m) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i <= m; i++) {
sb.append(list[i]).append(",");
}
if (sb.length() > 0) {
sb.setLength(sb.length() - 1);
}
arrangeList.add(sb.toString());
total++;
} else {
for (int i = k; i <= m; i++) {
swap(list, k, i);
perm(list, k + 1, m);
swap(list, k, i);
}
}
}
public int getTotal() {
return total;
}
public ArrayList<String> getArrangeList() {
return arrangeList;
}
public static void main(String args[]) {
// String list[] = { "1", "2", "3", "4", "5" };
String list[] = { "1", "2", "3" };
Arrange ts = new Arrange();
ts.perm(list, 0, list.length - 1);
for (int i = 0; i < ts.getArrangeList().size(); i++) {
System.out.println(ts.getArrangeList().get(i));
}
System.out.println("total:" + ts.total);
}
}
分享到:
相关推荐
组合数学之排列组合生成算法,很好的学习组合排列算法的资料
数字排列组合是个经典的算法问题,它很通俗易懂,适合不懂业务的人学习,我们通过它来发现和运用并行计算的优势,可以得到一个很直观的体会,并留下深刻的印象。问题如下: 请写一个程序,输入M,然后打印出M个...
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
实现全排列组合的算法,供大家学习与参考。在需要对排列组合做差异分析的时候可以直接使用。例如:几个正则式的不同排列组合对匹配效果的影响
leetcode爬楼梯排列组合解法 Data Structure and Algorithmic Practice 【任务1 - 数组与链表】 1、数组 实现一个支持动态扩容的数组 实现一个大小固定的有序数组,支持动态增删改操作 实现两个有序数组合并为一个...
圆排列问题的蚁群模拟退火算法 智能混合优化策略及其在流水作业调度中的应用 蚁群算法在QoS网络路由中的应用 一种改进的自适应路由算法 基于蚁群算法的煤炭运输优化方法 基于蚁群智能和支持向量机的人脸性别分类...
模拟退火算法解决置换流水车间调度问题(python实现) Use Simulated Annealing Algorithm for the basic Job Shop Scheduling Problem With Python 作业车间调度问题(JSP)是计算机科学和运筹学中的一个热门优化问题...
产生组合的非递归算法 大整数的乘法 对LZW算法的改进及其在图象无损压缩中的应用 复数快速傅立叶变换算法 加密算法与密钥管理 经典加密算法在VB中的实现(1)- Rsa 经典加密算法在VB中的实现(2)- MD5 经典加密算法...
2,双色球彩票游戏软件,该实例详细介绍了产生随机数的算法和排列组合算法,以及VC如何操作EXCEL 3,超级记事本,该实例详细介绍控件,记录,显示,编辑和保存的使用 4,友情通信录,该实例详细介绍VC读写文件的方式 5,快乐...
学习编程的人都知道,阅读、剖析名家代码乃是提高水平的捷径。...你将看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现;你甚至能够看到底层的memory pook和高阶抽象的traits机制的实现。
侯捷 版本 STL源码剖析 C++ 学习不二经典 学习编程的人都知道,阅读、剖析名家...看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现;甚至还能够看到底层的memory pool和高阶抽象的traits机制的实现。
本书旨在探讨如何优化算法效率,详细阐述了经典算法和特殊算法的实现、应用技巧和复杂度验证过程,内容由浅入深,能帮助读者快速掌握复杂度适当、正确率高的高效编程方法以及自检、自测技巧,是参加ACM ICPC、Google...
学习编程的人都知道,阅读、剖析名家代码乃是提高水平的捷径。...看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现;甚至还能够看到底层的memory pook和高阶抽象的traits机制的实现。
学习编程的人都知道,阅读、剖析名家代码乃是提高水平的捷径。...看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现;甚至还能够看到底层的memory pool和高阶抽象的traits机制的实现。
学习编程的人都知道,阅读、剖析名家代码乃是提高水平的捷径。...看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现;甚至还能够看到底层的memory pool和高阶抽象的traits机制的实现
学习编程的人都知道,阅读、剖析名家代码乃是提高水平的捷径。...看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现;甚至还能够看到底层的memory pool和高阶抽象的traits机制的实现。
学习编程的人都知道,阅读、剖析名家代码乃是提高水平的捷径。...看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现;甚至还能够看到底层的memory pool和高阶抽象的traits机制的实现。
学习编程的人都知道,阅读、剖析名家代码乃是提高水平的捷径。...看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现;甚至还能够看到底层的memory pool和高阶抽象的traits机制的实现。
学习编程的人都知道,阅读、剖析名家代码乃是提高水平的捷径。...看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现;甚至还能够看到底层的memory pool和高阶抽象的traits机制的实现。