第六天：分组

[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);

不想直接给答案，有订阅的大家思考一下，有兴趣的可以评论发自己的答案。也是留给老婆的一道题。考点包括随机、数组操作、基本的流程控制。

补：昨天又忘记了 ( 👎 )

[csvwolf]

我的思路是，首先先随机排序，之后保证每组人数相对较均匀即可，请小鱼老师多多指教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);

[nimoc]

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)

[sofish]

分享一个我的思路：

'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/

[rccoder]

@sofish

鱼大大，假如这四个组是有区别的，你上面的这种写法貌似还是存在一些问题

每次入组的时候 都是 依次从 0/1/2 组开始入，这样最后永远是前面的几个组人数比后面几个组的人数多一个

---

不过感觉大大的代码好有感觉，好精干......

[sofish]

@rccoder 嗯，如果需要有顺序排列的话，后面再重新「洗牌」就可以了：

group.sort(() => Math.random() * 2 - 1)

[rccoder]

@sofish 👍

[jununx]

@sofish

鱼大大的代码，短小精干啊。

[jununx]

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);

[lljxx1]

'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);

[xiaoqiang730730]

码个

(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);

[toplan]

@sofish 👍 入组的时候哇感觉这样更简洁：

...
  group[i % size].push(arr.splice(index, 1)[0]);    
...