标题:从n个整数中找出y个整数,输出全体结成。
标题:从n个整数中找出y个整数,输出全部组成。
譬如:一,贰,叁 这几个集合找出1个整数,组合有:一,二; 1,三; 二,3 共三种景况
譬如:一,二,3 这么些集合找出3个整数,组合有:1,贰; 壹,三; 2,三 共两种情况
实现:
实现:
思路:
能够想象成彩投票公投球,例如双色球,从3三个球中甄选多少个球出来,第2遍有3③种或许,第1遍有3二种恐怕….,举个简单例子,从一,2,三以此集合中选出二个数,如图所示
思路:
能够设想成彩投票大选球,例如双色球,从三二十一个球中甄选七个球出来,第三次有3三种也许,第二次有3贰种恐怕….,举个简易例子,从一,二,三以此集合中选出1个数,如图所示
具体的java完毕代码如下:
现实的java落成代码如下:
package com.hdwang;
import java.util.ArrayList;
import java.util.List;
/**
* Created by hdwang on 2016/12/26.
*/
public class Combine {
/**
* 集合(球)
*/
int[] ball;
/**
* 排列子集
*/
List<String> subColListPL = new ArrayList<String>();
/**
* 组合子集
*/
List<String> subColListCH = new ArrayList<String>();
/**
* 子集大小(元素个数)
*/
int subSize = 1;
Combine(int size,int subSize){
//初始化集合
this.ball = new int[size];
for(int i=0;i<size;i++){
this.ball[i] = i+1;
// this.ball[i] = i;
}
//定义子集大小
this.subSize = subSize;
}
/**
* 产生子集
*/
public void generateSubCol(){
//选择第一个球
for(int i=0;i<ball.length;i++){
int[] subBall = new int[this.subSize]; //由n个数组暂存子集元素
subBall[0] = ball[i]; //子集第一个球的选择
forFunc(subBall,1); //设置子集第二个球
}
//打印排列
System.out.println("打印排列集合:");
for(int i=0;i< this.subColListPL.size();i++){
System.out.print(subColListPL.get(i));
System.out.print("; ");
}
//找出组合
for(int i=0;i<this.subColListPL.size();i++){
String subColStr = subColListPL.get(i);
subColStr = sortSubCol(subColStr); //对子集排序一下(组合按照从小大小的规则输出)
if(!this.subColListCH.contains(subColStr)){ //去重
this.subColListCH.add(subColStr);
}
}
//打印组合
System.out.println("\n打印组合集合:");
for(int i=0;i< this.subColListCH.size();i++){
System.out.print(subColListCH.get(i));
System.out.print("; ");
}
}
/**
* 循环方法
* @param subBall 子集
* @param index 子集将设置值的位置
*/
private void forFunc(int[] subBall,int index){
if(index == this.subSize){ //某一种排列产生
String subBallStr = this.join(subBall);
this.subColListPL.add(subBallStr);
return; //退出递归
}
int remainBallLen = ball.length-index; //剩余可选球个数
int[] availableBall = new int[remainBallLen];
int j=0;
for(int i=0;i<ball.length;i++){
int preLen = index; //subBall前多少个球已选
if(!contains(subBall,ball[i],preLen)){ //不在子集中的球
availableBall[j] = ball[i];
j++;
}
}
for(int i=0;i<availableBall.length;i++){
subBall[index] = availableBall[i]; //指定位置赋值(选第index+1个球)
forFunc(subBall, index + 1); //递归调用
subBall[index] = 0; //恢复值(可略)
}
}
/**
* 数组前几个元素是否等于某值
* @param array 数组
* @param value 值
* @param preLen 前几个元素
* @return 是否存在
*/
private boolean contains(int[] array,int value,int preLen){
boolean c = false;
if(array == null){
return false;
}
for(int i=0;i<preLen;i++){
if(array[i] == value){
c = true;
break;
}
}
return c;
}
/**
* 数组转字符串
* @param array 数组
* @return 字符串(逗号分隔)
*/
public String join(int[] array){
String str ="";
for(int i=0;i<array.length;i++){
str += array[i]+",";
}
return str.substring(0,str.length()-1);
}
/**
* 子集排序一下(例如: 1,3,2 -> 1,2,3 )
* @param subColStr 子集字符串
* @return 排序后的字符串
*/
private String sortSubCol(String subColStr) {
String[] subcolArray = subColStr.split(",");
int[] subcol = new int[subcolArray.length];
for(int i=0;i<subcolArray.length;i++){
subcol[i] = Integer.parseInt(subcolArray[i]);
}
sort(subcol);
return join(subcol);
}
/**
* 冒泡排序
* @param array 整型数组
*/
public void sort(int[] array){
for(int i=0;i< array.length-1;i++){ //比多少次
for(int j= i+1;j<array.length;j++){ //每次循环,将最小数置前
if(array[i]>array[j]){ //小数冒泡
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
}
}
package com.hdwang;
import java.util.ArrayList;
import java.util.List;
/**
* Created by hdwang on 2016/12/26.
*/
public class Combine {
/**
* 集合(球)
*/
int[] ball;
/**
* 排列子集
*/
List<String> subColListPL = new ArrayList<String>();
/**
* 组合子集
*/
List<String> subColListCH = new ArrayList<String>();
/**
* 子集大小(元素个数)
*/
int subSize = 1;
Combine(int size,int subSize){
//初始化集合
this.ball = new int[size];
for(int i=0;i<size;i++){
this.ball[i] = i+1;
// this.ball[i] = i;
}
//定义子集大小
this.subSize = subSize;
}
/**
* 产生子集
*/
public void generateSubCol(){
//选择第一个球
for(int i=0;i<ball.length;i++){
int[] subBall = new int[this.subSize]; //由n个数组暂存子集元素
subBall[0] = ball[i]; //子集第一个球的选择
forFunc(subBall,1); //设置子集第二个球
}
//打印排列
System.out.println("打印排列集合:");
for(int i=0;i< this.subColListPL.size();i++){
System.out.print(subColListPL.get(i));
System.out.print("; ");
}
//找出组合
for(int i=0;i<this.subColListPL.size();i++){
String subColStr = subColListPL.get(i);
subColStr = sortSubCol(subColStr); //对子集排序一下(组合按照从小大小的规则输出)
if(!this.subColListCH.contains(subColStr)){ //去重
this.subColListCH.add(subColStr);
}
}
//打印组合
System.out.println("\n打印组合集合:");
for(int i=0;i< this.subColListCH.size();i++){
System.out.print(subColListCH.get(i));
System.out.print("; ");
}
}
/**
* 循环方法
* @param subBall 子集
* @param index 子集将设置值的位置
*/
private void forFunc(int[] subBall,int index){
if(index == this.subSize){ //某一种排列产生
String subBallStr = this.join(subBall);
this.subColListPL.add(subBallStr);
return; //退出递归
}
int remainBallLen = ball.length-index; //剩余可选球个数
int[] availableBall = new int[remainBallLen];
int j=0;
for(int i=0;i<ball.length;i++){
int preLen = index; //subBall前多少个球已选
if(!contains(subBall,ball[i],preLen)){ //不在子集中的球
availableBall[j] = ball[i];
j++;
}
}
for(int i=0;i<availableBall.length;i++){
subBall[index] = availableBall[i]; //指定位置赋值(选第index+1个球)
forFunc(subBall, index + 1); //递归调用
subBall[index] = 0; //恢复值(可略)
}
}
/**
* 数组前几个元素是否等于某值
* @param array 数组
* @param value 值
* @param preLen 前几个元素
* @return 是否存在
*/
private boolean contains(int[] array,int value,int preLen){
boolean c = false;
if(array == null){
return false;
}
for(int i=0;i<preLen;i++){
if(array[i] == value){
c = true;
break;
}
}
return c;
}
/**
* 数组转字符串
* @param array 数组
* @return 字符串(逗号分隔)
*/
public String join(int[] array){
String str ="";
for(int i=0;i<array.length;i++){
str += array[i]+",";
}
return str.substring(0,str.length()-1);
}
/**
* 子集排序一下(例如: 1,3,2 -> 1,2,3 )
* @param subColStr 子集字符串
* @return 排序后的字符串
*/
private String sortSubCol(String subColStr) {
String[] subcolArray = subColStr.split(",");
int[] subcol = new int[subcolArray.length];
for(int i=0;i<subcolArray.length;i++){
subcol[i] = Integer.parseInt(subcolArray[i]);
}
sort(subcol);
return join(subcol);
}
/**
* 冒泡排序
* @param array 整型数组
*/
public void sort(int[] array){
for(int i=0;i< array.length-1;i++){ //比多少次
for(int j= i+1;j<array.length;j++){ //每次循环,将最小数置前
if(array[i]>array[j]){ //小数冒泡
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
}
}
调用示例:
调用示例:
package com.hdwang;
/**
* Created by admin on 2016/12/26.
* 组合测试
*/
public class CombineTest {
public static void main(String[] args){
Combine combine = new Combine(3,2);
combine.generateSubCol();
// int[] array = {3,1};
// combine.sort(array);
// System.out.println(combine.join(array));
}
}
package com.hdwang;
/**
* Created by admin on 2016/12/26.
* 组合测试
*/
public class CombineTest {
public static void main(String[] args){
Combine combine = new Combine(3,2);
combine.generateSubCol();
// int[] array = {3,1};
// combine.sort(array);
// System.out.println(combine.join(array));
}
}
出口结果:
出口结果:
打印排列集合:
1,2; 1,3; 2,1; 2,3; 3,1; 3,2;
打字与印刷组合集合:
1,2; 1,3; 2,3;
打字与印刷排列集合:
1,2; 1,3; 2,1; 2,3; 3,1; 3,2;
打字与印刷组合集合:
1,2; 1,3; 2,3;