如何有效地随机选择数组项而不重复？

Question

我知道这个问题在许多方面存在,但我无法找到与我的具体效率问题相关的答案.

我有下面的代码,工作得很好.

我有一个10项数组,我从中随机选择一个项目(按下输入键).代码保留了最近5个选项的数组,这些选择不能随机选择(以避免随着时间的推移重复过多).

如果chooseName()函数最初选择在最近的5中使用的名称,它只会断开并再次调用自身,重复直到找到"唯一"名称.

我有两个问题:

1. 说这是一个"递归函数"是否正确？

2. 我担心理论上这可能会在找到一个唯一名称之前保持循环很长时间 - 是否有更有效的方法来执行此操作？

感谢您的任何帮助.

    var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"];
    var b = [];

    var chooseName = function () {
    var unique = true;
    b.length = 5;
    num = Math.floor(Math.random() * a.length);
    name = a[num];    
        for (i = 0; i < a.length; i++) {
        if (b[i] == name) {
            chooseName();
            unique = false;
            break;
            }
        }
        if (unique == true) {
        alert(name);
        b.unshift(name);
        }
    }


    window.addEventListener("keypress", function (e) {
        var keycode = e.keyCode;
        if (keycode == 13) {
        chooseName();
        }
    }, false);

Answer 1

我喜欢评论者@YuriyGalanter关于随机选择项目直到所有项目都被重复的想法,所以这是一个实现:

function randomNoRepeats(array) {
  var copy = array.slice(0);
  return function() {
    if (copy.length < 1) { copy = array.slice(0); }
    var index = Math.floor(Math.random() * copy.length);
    var item = copy[index];
    copy.splice(index, 1);
    return item;
  };
}

var chooser = randomNoRepeats(['Foo', 'Bar', 'Gah']);
chooser(); // => "Bar"
chooser(); // => "Foo"
chooser(); // => "Gah"
chooser(); // => "Foo" -- only repeats once all items are exhausted.

Answer 2

每当选择一个项目时,将其移动到数组的后面,并从原始数组的切片中随机选择array.slice(0, -5).

var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"];

var chooseName = function () {
    var unique = true;
    num = Math.floor(Math.random() * a.length - 5);
    name = a.splice(num,1);
    a.push(name);
}


window.addEventListener("keypress", function (e) {
    var keycode = e.keyCode;
    if (keycode == 13) {
        chooseName();
    }
}, false);

编辑:这也有副作用,即不给出任何变量发生在列表中的不公平的缺点,即在前N个调用中不会考虑它们.如果这对您来说是个问题,可以尝试在某处保持一个静态变量来跟踪要使用的切片的大小,并在B处最大化(在本例中为5).例如

var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"];
B = 5; //max size of 'cache'
N = 0;

var chooseName = function () {
    var unique = true;
    num = Math.floor(Math.random() * a.length - N);
    N = Math.min(N + 1, B);
    name = a.splice(num,1);
    a.push(name);
}

Answer 3

我推荐你使用underscore.js，它会很简单。

该函数shuffle以均匀分布的方式实现，因此如果数组a包含更多数据，则重复的概率将较低。

var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"];
b = _.shuffle(a).slice(0,5);
console.log(b);