Fisher-Yates-shuffle洗牌算法

Fisher-Yates-shuffle洗牌算法

最近在看underscorejs的时候看到了.shuffle (打乱集合)用的就是这个Fisher-Yates-shuffle算法,然后在.simple(取样,从集合中随机取n个元素)中很好的依赖了_.shuffle

我不由得想起以前写通信软件基础作业的时候懵逼懵逼的想从数组中随机取n个元素该怎么 避免随机数重复

以下是underscore中的实现

shuffle:

_.shuffle = function(obj) {
    var set = obj && obj.length === +obj.length ? obj : _.values(obj);
    var length = set.length;
    var shuffled = Array(length);
    for (var index = 0, rand; index < length; index++) {
        rand = _.random(0, index);     // 产生0到index的随机数
        if (rand !== index) 
            shuffled[index] = shuffled[rand];
        shuffled[rand] = set[index];
    }
    return shuffled;
 };

sample:

 _.sample = function(obj, n, guard) {
    if (n == null || guard) {
        if (obj.length !== +obj.length) obj = _.values(obj);
        return obj[_.random(obj.length - 1)];
    }
    return _.shuffle(obj).slice(0, Math.max(0, n));
};

sample依赖于shuffle,先用shuffle將集合打乱,再从中取出n个元素,这个效果就和从集合中任取n个元素是一样的了,不得不说这个依赖很巧妙,反正我是没想到过.

以下简绍一下shuffle的算法

参考: Fisher-Yates-shuffle --wikipedia

-- Ming