learn-js
learn-js copied to clipboard
sofish
第六天：分组
几乎每次面试都问一个题：一群人出去玩，写一个程序随机分组可以如何分。最后简化成 10 个人出去玩，如何将人随机分配到 4 个组里，并保证每个组的人比较均匀。
var arr = [1,2,3,4,5,6,7,8,9,0];
var group = [[],[],[],[]];
(function split(arr, group) {
// you code here
console.log(group);
})(arr, group);
不想直接给答案，有订阅的大家思考一下，有兴趣的可以评论发自己的答案。也是留给老婆的一道题。考点包括随机、数组操作、基本的流程控制。
补：昨天又忘记了 ( 👎 )
我的思路是，首先先随机排序，之后保证每组人数相对较均匀即可，请小鱼老师多多指教QuQ
var arr = [1,2,3,4,5,6,7,8,9,0];
var group = [[],[],[],[]];
(function split(arr, group) {
// you code here
var groupSize = group.length,
totalSize = arr.length;
// 随机排序
arr.sort(function() {
return Math.random() * 2 - 1;
});
// 接下来保证每组数量比较平均即可
group.forEach(function(elem, index) {
var size = Math.floor(totalSize / groupSize);
for (var i = 0; i < size; i++) {
elem.push(arr.pop());
}
totalSize -= size;
groupSize--;
});
console.log(group);
})(arr, group);
var arr = [1,2,3,4,5,6,7,8,9,0]
var group = [[],[],[],[]]
function shuffle (arr) {
return arr.sort(function () {
return Math.round(Math.random())
})
}
;(function split(arr, group) {
// 打乱数组
var randomArr = shuffle(arr)
// 向下舍入的平均整数
var floorAverage = Math.floor(randomArr.length/group.length)
// 先按平均整数分配蛋糕
var output = group.map(function () {
item = randomArr.splice(0,floorAverage)
return item
})
// 如果还有蛋糕遍历一遍分配给所有人（没分到的算倒霉）
if (randomArr.length) {
output = output.map(function (item) {
item = item.concat(randomArr.splice(0,1))
return item
})
}
// 再次洗牌避免永远是前几个蛋糕多，后几个蛋糕少
output = shuffle(output)
console.log(JSON.stringify(output))
// [[3,5,8],[7,1],[4,2,9],[6,0]]
})(arr, group)
分享一个我的思路：
'use strict'
var arr = [1,2,3,4,5,6,7,8,9,0];
var group = [[],[],[],[]];
(function split(arr, group) {
var size = group.length; // 分多少组
var length = arr.length; // 人数总长度
// 每次随机叫一个人，跳进一个组里，并从原数组里踢掉
while(arr.length) {
for(let i = 0; i < length; i++){
let index = Math.random() * arr.length | 0; // 随机
group[i % size].push(arr[index]); // 入组
arr.splice(index, 1); // 踢掉
}
}
console.log(group);
})(arr, group);
补充：分享一个 Fisher-Yates 算法 https://bost.ocks.org/mike/shuffle/
@sofish
鱼大大，假如这四个组是有区别的，你上面的这种写法貌似还是存在一些问题
每次入组的时候 都是 依次从 0/1/2 组开始入，这样最后永远是前面的几个组人数比后面几个组的人数多一个
不过感觉大大的代码好有感觉，好精干......
@rccoder 嗯，如果需要有顺序排列的话，后面再重新「洗牌」就可以了：
group.sort(() => Math.random() * 2 - 1)
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
var group = [[], [], [], [] ];
;(function split(arr, group) {
// 借用了楼上nimojs的打乱数组
function shuffle(arr) {
return arr.sort(function() {
return Math.round(Math.random())
})
}
arr = shuffle(arr);
// 找到要添加的组下标
function filterGroupIndex() {
var res = group.map(function(v) {
return v.length;
});
return res.indexOf(Math.min.apply(null, res));
}
// 分组
arr.forEach(function(v) {
group[filterGroupIndex()].push(v);
});
console.log(JSON.stringify(shuffle(group)));
})(arr, group);
'use strict'
var arr = [1,2,3,4,5,6,7,8,9,0];
var group = [[],[],[],[]];
(function split(arr, group) {
// you code here
var personSize = arr.length;
var groupSize = group.length;
var average = Math.floor(personSize / groupSize);
function getPerson(){
return arr.shift();
}
function isLastPerson(){
return arr.length == 1;
}
function getGroup(index){
return group[index]
}
function getRandomGroup(){
var index = Math.floor(Math.random() * groupSize + 1)-1;
var groupL = group[index].length;
if(groupL < average || isLastPerson()){
return index;
}else{
return getRandomGroup();
}
}
function addToGroup(per){
var index = getRandomGroup()
group[index].push(per);
}
(function main(){
var per = getPerson();
if(!per) return;
addToGroup(per);
main();
})();
console.log(group);
})(arr, group);
码个
(function(arr, group) {
var arr = [1,2,3,4,5,6,7,8,9,0];
var group = [[],[],[],[]];
var random = function(arr) { // 打乱函数
return arr.sort(function() {
return Math.round(Math.random()*2) - 1;
});
}
var getRandom = function(arr) {// 分配
arr = random(arr);
return arr.splice(0, 1);
};
var len = Math.round(arr.length/group.length); // 分配轮数
for (var i = 0; i < len; i++) {
group.forEach(function(ele, index) { // 每轮依次分配
if(!arr.length) return group;
ele.push(getRandom(arr));
});
}
})(arr, group);
@sofish 👍 入组的时候哇感觉这样更简洁：
...
group[i % size].push(arr.splice(index, 1)[0]);
...
