你的位置:首页 > Java教程

[Java教程]一个简单的“将ball个球放到box各盒子中,每个盒子不多于m个,并且满足limit条件的状态”的函数


前段时间,做了一个某游戏的辅助计算工具,其中遇到一个排列组合问题。抽象出来就是

将ball个球放到box各盒子中,每个盒子不多于m个,并且满足limit条件,

请给出所有的这些状态。

随意找了下没有现成的,于是就自己写一个算了......

纠结了一段时间,发现其实就是一个普通的八皇后问题。

//将ball个球放到box各盒子中,每个盒子不多于m个,并且满足limit条件的状态//盒子状态使用长为box的数字字符串表示。//limit为类似于"0110000"的数字字符串(其表示条件是第1位和第1位至少为1),其末尾的0可省略//返回有盒子状态字符串组成的数组。function ballInBox(ball,box,m,limit){	var t='';//存放盒子状态的临时变量	var t1='';//存放根据当前状态计算出下一步状态的临时变量	var r=[];//返回数据用数组	var s=[];//存放对应的r状态的盒子中球的总数	var s1=0;//存放从s中取出的第一个状态	var l=0;//储存r的长度的临时变量		//初始化t为一个长度为box的全0字符串	for(var i = 0;i<box;i++)	{		t+='0';		}	//初始化r	r.push(t);	s.push(0);		//console.log(r);	//console.log(s);		//循环ball次。模拟ball个球以此放入盒子,并使用r来承接每次模拟后的结果集。	//每次模拟是从r中取出一个n个球已知状态,并将第n+1个球放入,并将所有放入结果在送回r中。	//模拟放入时从前向后顺,	//因为球没有差别,如果发现该盒子中已经有球了,就判断该盒子是否能再装入球,同时该球不再模拟此状态(跳转到下一状态)		for(var i =0;i<ball;i++)	{		while(true)		{			//console.log(r);			//console.log(s);			//如果当前状态的球数大于本次循环的球数(i),表示本球已经遍历完成了,该模拟下一球了			if(s[0]>i)				break;			//将最头上的取出,并尝试在该状态基础上,将球依次放入其中的盒子。每成功一次就将成功后的结果存入r中。			//共循环box次,即最多把盒子都循环一边。但如果遇到已经有球的盒子,便尝试放入后退出循环			//为保持模版状态的纯洁度,使用t1作为临时变量			t=r.shift();			s1=s.shift();			for(var j=0;j<box;j++)			{				if(t[j]==0)				{					t1=t.split('');					t1[j]=1;					t1=t1.join('');					r.push(t1);					s.push((s1+1));				}				else if(t[j]<m)				{					t1=t.split('');					t1[j]=parseInt(t1[j])+1;					t1=t1.join('');					r.push(t1);					s.push((s1+1));					break;				}				else if(t[j]<=m)				{					break;				}				else				{					return false;					}			}					}			}		//最后根据limit参数再过滤一遍	if(limit)	{		for(var i=0;i<r.length;i++)			{			for(var j=0;j<limit.length;j++)			{				if(r[i][j]<limit[j])				{					r.splice(i,1);					s.splice(i,1);					i--;					break;									}			}		}	}	return r;}