Javascript：如何有效地随机选择数组项没有重复

我知道这个问题是在许多伪装周围，但我一直没能找到一个有关我的具体问题的效率的答案。Javascript：如何有效地随机选择数组项没有重复

我有下面的代码，工作得很好。

我有一个10项数组，从中随机选择一个项目（在输入按键上）。该代码保留了最近5个不能随机选择的选项（以避免随着时间的过去重复）。

如果chooseName（）函数最初选择最近使用过的名称，它会简单地中断并重新调用自身，直到找到“唯一”名称为止。

我有两个问题：

难道是正确的说这是一种“递归函数”？
我很担心，理论上这可能会在找到一个独特的名称之前保持循环很长时间 - 是否有更高效的方法来执行此操作？

谢谢你的帮助。

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

来源

2013-07-26 Russell

一旦选择了它，创建数组的临时副本并从中简单地移除元素会怎样？当临时数组为空时 - 重新创建它。通过这种方式，您将永远不会重复，直到数组被删除 –

当您从数组中选择一个项目时，请将其删除，以免再次选中它，并将其添加到所选项目的数组中。当数组大于5时，将最老的数组添加回原始数组，以便可以再次选择它。 – Barmar

每当选择了一个项目，将它移动到阵列的背面，并从原始阵列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); 
}

来源

2013-07-26 21:23:57 smakateer

我推荐你使用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);

来源

2013-07-26 21:30:05 zsong

谢谢。我目前正试图远离图书馆，因为我想学习纯粹的JavaScript，以确保我知道发生了什么。我会在将来查看它。 – Russell

当你实例洗牌，给它的数组作为参数。它会创建一个数组的副本，并且每次调用next（）时，它都会从副本返回一个随机元素，并将其从副本数组中移除，以避免重复。

var Shuffler = function(a) { 
    var aCopy = [], 
     n  = 0; 

    // Clone array 
    for (n=0; n<a.length; n++) { 
     aCopy.push(a[n]); 
    } 

    this.next = function() { 
     if (aCopy.length == 0) { return null; } 

     var nRandom = Math.floor(Math.random() * (aCopy.length + 1)), 
      mElement = aCopy[nRandom]; 

     delete aCopy[nRandom]; 
     return mElement; 
    } 
} 

var oShuffler = new Shuffler([/* names go here */]), 
    sRandomName = null; 

while (sRandomName = oShuffler.next()) { 
    console.log(sRandomName); 
}

来源

2013-07-26 21:30:30

我喜欢评论者@直到全部取，然后才重复随机选择项目的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.

来源

2013-07-26 21:34:41 maerics

不错，我在用这个！ –