灯的排列问题：设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，……Nk（k表示不同颜色灯的个数）。
放灯时要遵守下列规则：
① 同一种颜色的灯不能分开；
② 不同颜色的灯之间至少要有一个空位置。
例如：N=8（格子数）
R=2（红灯数）
B=3（蓝灯数）
放置的方法有： 放置的总数为12种。
数据输入的方式为：
N
P1（颜色，为一个字母） N1（灯的数量）
P2 N2
……
Q（结束标记，Q本身不是灯的颜色） 程序要求：求出一种顺序的排列方案及排列总数。
放灯时要遵守下列规则：
① 同一种颜色的灯不能分开；
② 不同颜色的灯之间至少要有一个空位置。
例如：N=8（格子数）
R=2（红灯数）
B=3（蓝灯数）
放置的方法有： 放置的总数为12种。
数据输入的方式为：
N
P1（颜色，为一个字母） N1（灯的数量）
P2 N2
……
Q（结束标记，Q本身不是灯的颜色） 程序要求：求出一种顺序的排列方案及排列总数。
则结果应为：k!*(∁_(k+1)^1+∁_(k+1)^2+⋯+∁_(k+1)^m)思路：先把Nx(1<=x<=k)分别当做一个整体做全排列，即k!
m表示还剩下的空格
(∁_(k+1)^1+∁_(k+1)^2+⋯+∁_(k+1)^m)表示将m个空格分别分成x(1<=x<=m)块插入到k+1个由k种颜色隔开的位置
∁_(k+1)^1表示组合的符号，浏览器显示问题，挺好理解的
char lampColor;
int lampNum;
Lamp(char c,int n){
lampColor=c;
lampNum=n;
}
public String toString(){
StringBuilder result=new StringBuilder();
for(int i=0;i<lampNum;i++){
result.append(lampColor);
}
return result.toString();
}
}public class Test{
private static int counter=0;
public static void main(String args[]) throws Exception {
List<Lamp> lampList=new ArrayList<Lamp>(){{
add(new Lamp('R',2));
add(new Lamp('B',3));
}};
char[] grids=new char[8];
for(int i=0;i<grids.length;i++){
grids[i]=' '; }
lampProblem(lampList,grids,0);
System.out.println("共有"+counter+"种结果");
}
public static void lampProblem(List<Lamp> lamps,char[] grids,int num){
if(lamps.size()==num){
counter++;
System.out.println(Arrays.toString(grids));
return;
}
Lamp lamp=lamps.get(num); for(int pos=0;pos<grids.length;){
if(grids[pos]!=' '){
pos++;
continue;
}
//找一个合适的位置把lamp放下:
//
if(pos-1>=0&&grids[pos-1]!=' '){
pos++;
}
if(pos+lamp.lampNum>grids.length){
break;
}
boolean canPlace=true;
int index;
for(index=pos+1;index<pos+lamp.lampNum;index++){
if(grids[index]!=' '){
canPlace=false;
break;
}
}
if(canPlace&&(index==grids.length||grids[index]==' ')){
for(int i=pos;i<lamp.lampNum+pos;i++){
grids[i]=lamp.lampColor;
}
lampProblem(lamps,grids,num+1);
for(int i=pos;i<lamp.lampNum+pos;i++){
grids[i]=' ';
}
pos++;
}else{
pos=index;
}
}
}
}F:\java>java Test
[R, R, , B, B, B, , ]
[R, R, , , B, B, B, ]
[R, R, , , , B, B, B]
[ , R, R, , B, B, B, ]
[ , R, R, , , B, B, B]
[ , , R, R, , B, B, B]
[B, B, B, , R, R, , ]
[B, B, B, , , R, R, ]
[ , B, B, B, , R, R, ]
[B, B, B, , , , R, R]
[ , B, B, B, , , R, R]
[ , , B, B, B, , R, R]
共有12种结果
F:\java>java Test
[R, R, , B, B, , Y, Y]
[R, R, , Y, Y, , B, B]
[B, B, , R, R, , Y, Y]
[Y, Y, , R, R, , B, B]
[B, B, , Y, Y, , R, R]
[Y, Y, , B, B, , R, R]
共有6种结果