【问题】
现有2个红球,2个黄球,3个白球,3个黑球,同色球不加区分,将十个球排成一列,有多少种不同的方法?
【数学分析】
上面的关键就是“同色球不加区分”这句,这句话的潜台词就是“选出的结果无需排列”。
人排队肯定是排列的,因为有很多属性不一样,但两个同样规格的球不需要,因为所有属性都一致。
接下来就是:十个位置里选出2个放红球,8个位置里选出2个放黄球,6个位置里选出3个放白球,3个位置里选三个放黑球,总的方案是C10_2*C8_2*C6_3*C3_3=25200个。
你也可以十个位置里选出3个放黑球,7个位置里选出3个放白球,4个位置里选出2个放黄球,2个位置里选2个放红球,总的方案是C10_3*C7_3*C4_2*C2_2=25200个。
选择颜色可以随意,但结果都一样。
【程序解法】
使用三次Combination类,用三重循环,进行前三种颜色的选择与剔除,没处理的就是黑色。
辅助类 Combination:
package test230902;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* 数学中排列组合中的组合器实现
* 传入一个数组及选择的个数,传出所有选择方案
*/
class Combination {
/**
* 用于存放中间结果
*/
private Stack<Integer> stack;
/**
* 用于存放结果
*/
private List<List<Integer>> results;
/**
* 构造函数
* @param arr 进行组合的元素
* @param count 选多少个
*/
public Combination(int[] arr,int count) {
if(count>arr.length) {
throw new ArrayIndexOutOfBoundsException(count+">"+arr.length);
}
stack = new Stack<>();
results=new ArrayList<>();
doSelect(arr,count,0,0);
}
/**
* 进行选择
* @param arr 目标数组
* @param expect 期望选择数量
* @param actual 实际选择数量
* @param current 当前下标
*/
private void doSelect(int[] arr, int expect, int actual, int current) {
if(actual == expect) {
List<Integer> list=new ArrayList<>();
for(int i:stack) {
list.add(i);
}
results.add(list);
return;
}
for(int i=current;i<arr.length;i++) {
if(!stack.contains(arr[i])) {
stack.add(arr[i]);
doSelect(arr, expect, actual+1, i);
stack.pop();
}
}
}
/**
* 取得组合结果
* @return
*/
public List<List<Integer>> getResults(){
return results;
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
final int[] arr= {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30};
final int count=2;
Combination c=new Combination(arr,count);
List<List<Integer>> results=c.getResults();
int idx=0;
for(List<Integer> res:results) {
System.out.println(String.format("%02d", ++idx) +"."+res);
}
}
}
主类 TenColorBall:
package test230902;
import java.io.BufferedWriter;
import java.io.FileOutputStream;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
/**
* 现有2个红球,2个黄球,3个白球,3个黑球
* 同色球不加区分,将十个球排成一列,有多少种不同的方法
* @author 逆火
*
*/
public class TenColorBall {
public static void main(String[] args) {
final int[] redArr= {0,1,2,3,4,5,6,7,8,9};
Combination redCbn=new Combination(redArr,2);// 10选2放红球
List<List<Integer>> redResults=redCbn.getResults();
List<String> sentences=new ArrayList<>();
int idx=0;
for(List<Integer> redResult:redResults) {
final int[] yellowArr= minus(redArr,redResult);// printArr(yellowArr);
Combination yellowCbn=new Combination(yellowArr,2);// 8选2放黄球
List<List<Integer>> yellowResults=yellowCbn.getResults();
for(List<Integer> yellowResult:yellowResults) {
final int[] whiteArr= minus(yellowArr,yellowResult);// printArr(whiteArr);
Combination whiteCbn=new Combination(whiteArr,3);// 6选3放白球
List<List<Integer>> whiteResults=whiteCbn.getResults();
for(List<Integer> whiteResult:whiteResults) {
String[] plans= {"黑","黑","黑","黑","黑","黑","黑","黑","黑","黑"};
for(int i:redResult) {
plans[i]="红";
}
for(int i:yellowResult) {
plans[i]="黄";
}
for(int i:whiteResult) {
plans[i]="白";
}
//System.out.println((++idx)+"."+String.join(",", plans));
String sentence=(String.format("%05d.", ++idx))+String.join(" ", plans);
sentences.add(sentence);
plans=null;
}
}
}
try {
FileOutputStream writerStream = new FileOutputStream("c:\\hy\\TenColorBall.txt");
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(writerStream, "UTF-8"));
for(String s:sentences) {
writer.write(s+"\n");
}
writer.close();
}catch(Exception ex) {
ex.printStackTrace();
}
}
/**
* 打印数组,测试用
* @param arr
*/
private static void printArr(int[] arr) {
for(int i:arr) {
System.out.print(i+",");
}
System.out.println();
}
private static void printArr2(String[] arr) {
for(String i:arr) {
System.out.print(i+",");
}
System.out.println();
}
/**
* 从原数组里去除多余的部分
* @param origins
* @param extras
* @return
*/
private static int[] minus(int[] origins,List<Integer> extras){
int[] arr=new int[origins.length-extras.size()];
int idx=0;
for(int i=0;i<origins.length;i++) {
int num=origins[i];
if(extras.contains(num)==false) {
arr[idx++]=num;
}
}
return arr;
}
}
【部分输出结果】
25155.黑 白 黑 白 黑 黄 黄 白 红 红
25156.黑 白 黑 黑 白 黄 黄 白 红 红
25157.黑 黑 白 白 白 黄 黄 黑 红 红
25158.黑 黑 白 白 黑 黄 黄 白 红 红
25159.黑 黑 白 黑 白 黄 黄 白 红 红
25160.黑 黑 黑 白 白 黄 黄 白 红 红
25161.白 白 白 黑 黑 黄 黑 黄 红 红
25162.白 白 黑 白 黑 黄 黑 黄 红 红
25163.白 白 黑 黑 白 黄 黑 黄 红 红
25164.白 白 黑 黑 黑 黄 白 黄 红 红
25165.白 黑 白 白 黑 黄 黑 黄 红 红
25166.白 黑 白 黑 白 黄 黑 黄 红 红
25167.白 黑 白 黑 黑 黄 白 黄 红 红
25168.白 黑 黑 白 白 黄 黑 黄 红 红
25169.白 黑 黑 白 黑 黄 白 黄 红 红
25170.白 黑 黑 黑 白 黄 白 黄 红 红
25171.黑 白 白 白 黑 黄 黑 黄 红 红
25172.黑 白 白 黑 白 黄 黑 黄 红 红
25173.黑 白 白 黑 黑 黄 白 黄 红 红
25174.黑 白 黑 白 白 黄 黑 黄 红 红
25175.黑 白 黑 白 黑 黄 白 黄 红 红
25176.黑 白 黑 黑 白 黄 白 黄 红 红
25177.黑 黑 白 白 白 黄 黑 黄 红 红
25178.黑 黑 白 白 黑 黄 白 黄 红 红
25179.黑 黑 白 黑 白 黄 白 黄 红 红
25180.黑 黑 黑 白 白 黄 白 黄 红 红
25181.白 白 白 黑 黑 黑 黄 黄 红 红
25182.白 白 黑 白 黑 黑 黄 黄 红 红
25183.白 白 黑 黑 白 黑 黄 黄 红 红
25184.白 白 黑 黑 黑 白 黄 黄 红 红
25185.白 黑 白 白 黑 黑 黄 黄 红 红
25186.白 黑 白 黑 白 黑 黄 黄 红 红
25187.白 黑 白 黑 黑 白 黄 黄 红 红
25188.白 黑 黑 白 白 黑 黄 黄 红 红
25189.白 黑 黑 白 黑 白 黄 黄 红 红
25190.白 黑 黑 黑 白 白 黄 黄 红 红
25191.黑 白 白 白 黑 黑 黄 黄 红 红
25192.黑 白 白 黑 白 黑 黄 黄 红 红
25193.黑 白 白 黑 黑 白 黄 黄 红 红
25194.黑 白 黑 白 白 黑 黄 黄 红 红
25195.黑 白 黑 白 黑 白 黄 黄 红 红
25196.黑 白 黑 黑 白 白 黄 黄 红 红
25197.黑 黑 白 白 白 黑 黄 黄 红 红
25198.黑 黑 白 白 黑 白 黄 黄 红 红
25199.黑 黑 白 黑 白 白 黄 黄 红 红
25200.黑 黑 黑 白 白 白 黄 黄 红 红
END
标签:230902,arr,String,Combination,int,List,黄球,不加区分,new From: https://blog.51cto.com/u_7726611/7335074