m选n的所有组合
思路
M选N组合算法
应用--×××的注数算法
创新互联公司致力于成都网站制作、成都网站建设,成都网站设计,集团网站建设等服务标准化,推过标准化降低中小企业的建站的成本,并持续提升建站的定制化服务水平进行质量交付,让企业网站从市场竞争中脱颖而出。 选择创新互联公司,就选择了安全、稳定、美观的网站建设服务!
本程序的思路是开一个数组b,其长度和数据数组一致,其前N位为1,N就是要取的数的个数,然后按照b的数据为1的下标来取数据数组的数字
然后从左到右扫描数组b元素值的“10”组合,找到第一个“10”组合后将其变为
“01”组合,同时将其左边的所有“1”全部移动到数组的最左端,“0”移到所有“1”和变为了“01”的中间
当b数组最右边的N个元素全部为1时 组合完毕
例如求5中选3的组合:
1 2 3 4 5 <-数组数组
1 1 1 0 0 -->1,2,3
1 1 0 1 0 -->1,2,4
1 0 1 1 0 -->1,3,4
0 1 1 1 0 -->2,3,4
1 1 0 0 1 -->1,2,5
1 0 1 0 1 -->1,3,5
0 1 1 0 1 -->2,3,5
1 0 0 1 1 -->1,4,5
0 1 0 1 1 -->2,4,5
0 0 1 1 1 -->3,4,5
打印所有组合时,做判断是1时赋值下标然后输出
public class MyCombine {
public static void main(String[] args) {
String[] a = { "1", "2", "3", "4", "5","6","7","8","9","10","11"};
int num = 5;
MyCombine tp = new MyCombine();
for (String obj : tp.combine(a, num)) {
//System.out.println(obj.toString());
break;
}
}
/**
- 实现的算法
- @param a 数据数组
- @param num M选N中 N的个数
- @return
*/
private List combine(String[] a, int num) {
List list = new ArrayList();
List list2 = new ArrayList();
StringBuffer sb = new StringBuffer();
String[] b = new String[a.length];
for (int i = 0; i < b.length; i++) {
if (i < num) {
b[i] = "1";
} else
b[i] = "0";
}
for(int i = 0; i < b.length; i++){
if(b[i]=="1"){
//list2.add(a[i]);
System.out.print(a[i]+",");
}
}
System.out.println("\n");
int point = 0;
int nextPoint = 0;
int count = 0;
int sum = 0;
String temp = "1";
while (true) {
// 判断是否全部移位完毕
for (int i = b.length - 1; i >= b.length - num; i--) {
if (b[i].equals("1"))
sum += 1;
}
// 根据移位生成数据
for (int i = 0; i < b.length; i++) {
if (b[i].equals("1")) {
point = i;
sb.append(a[point]);
sb.append(" ");
count++;
if (count == num)
break;
}
}
for(int i = 0; i < b.length; i++){
if(b[i]=="1"){
System.out.print(a[i]+",");
}
}
System.out.println("\n");
// 往返回值列表添加数据
list.add(sb.toString());
// 当数组的最后num位全部为1 退出
if (sum == num) {
break;
}
sum = 0;
// 修改从左往右第一个10变成01
for (int i = 0; i < b.length - 1; i++) {
if (b[i].equals("1") && b[i + 1].equals("0")) {
point = i;
nextPoint = i + 1;
b[point] = "0";
b[nextPoint] = "1";
break;
}
}
// 将 i-point个元素的1往前移动 0往后移动
for (int i = 0; i < point - 1; i++)
for (int j = i; j < point - 1; j++) {
if (b[i].equals("0")) {
temp = b[i];
b[i] = b[j + 1];
b[j + 1] = temp;
}
}
// 清空 StringBuffer
sb.setLength(0);
count = 0;
}
System.out.println("数据长度 " + list.size());
return list;
}
}
分享标题:m选n的所有组合
标题URL:
http://kswjz.com/article/piipce.html
扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流