前段时间,做了一个某游戏的辅助计算工具,其中遇到一个排列组合问题。抽象出来就是
将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;}
原标题:一个简单的“将ball个球放到box各盒子中,每个盒子不多于m个,并且满足limit条件的状态”的函数
关键词:函数