javascript 如何有效地随机选择数组项而不重复？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17891173/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to efficiently randomly select array item without repeats?
提问by Russell
I'm aware that this question is around in many guises but I have not been able to find an answer relating to my specific issue of efficiency.
我知道这个问题有多种形式，但我无法找到与我的具体效率问题相关的答案。
I have the below code that works just fine.
我有以下代码可以正常工作。
I have a 10 item array from which I randomly select an item (on enter key press). The code keeps an array of the 5 most recent choices which cannot be randomly selected (to avoid too much repetition over time).
我有一个 10 个项目的数组，我从中随机选择一个项目（按 Enter 键）。该代码保留了一个包含 5 个最新选项的数组，这些选项不能随机选择（以避免随着时间的推移重复太多）。
If the chooseName() function initially selects a name that has been used in the recent 5 goes it simply breaks and calls itself again, repeating until it finds a "unique" name.
如果chooseName() 函数最初选择了最近5 次使用过的名称，它只会中断并再次调用自己，重复直到找到“唯一”名称。
I have two questions:
我有两个问题：
Is it correct to say this is a "recursive function"?
I am worried that theoretically this could keep looping for a long time before finding a unique name - is there a more efficient way to do this?
说这是一个“递归函数”是否正确？
我担心理论上这可能会在找到唯一名称之前循环很长时间 - 有没有更有效的方法来做到这一点？
Thank you for any help.
感谢您的任何帮助。
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);
采纳答案by smakateer
Whenever an item is selected, move it to the back of the array and randomly select from a slice of the original array array.slice(0, -5).
Whenever an item is selected, move it to the back of the array and randomly select from a slice of the original array 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);
EDIT: This also has the side-effect of not giving whichever variables happen to tail the list the unfair disadvantage that they won't be considered in the first N calls. If that's a problem for you, maybe try hold a static variable somewhere to keep track of the size of the slice to use and max it out at B (in this case, 5). e.g.
编辑：这也有副作用，即不给任何发生在列表尾部的变量带来不公平的劣势，即在前 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);
}
回答by maerics
I like commenter @YuriyGalanter's idea of choosing items randomly until all are taken and only then repeating, so here's an implementation:
我喜欢评论者@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.
回答by zs2020
I recommend you to use underscore.js, it will be very simple.
我推荐你使用underscore.js，它会很简单。
The function shuffleis implemented in uniformly distributed way so the probability of repetition will be low if the array acontains more data.
该函数shuffle以均匀分布的方式实现，因此如果数组a包含更多数据，则重复的概率将较低。
var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"];
b = _.shuffle(a).slice(0,5);
console.log(b);
回答by Lex
When you instantiate Shuffler, give it your array as a parameter. It will create a copy of the array and every time next() is called it will return a random element from a copy and remove it from the copy array so that no repeats are possible.
当您实例化 Shuffler 时，将您的数组作为参数。它将创建数组的副本，每次调用 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);
}
回答by Mysha
Yes, this is recursive, and since it isn't diminishing the state it could theoretically go on forever.
是的，这是递归的，因为它不会减少状态，所以理论上它可以永远持续下去。
I assume changing the array is not allowed, as otherwise you could simply remove the recent choices from the array and push them back in as the recent choices buffer overflows.
我假设不允许更改数组，否则您可以简单地从数组中删除最近的选择，并在最近的选择缓冲区溢出时将它们推回。
Instead: Exclude buffersize items at the end of the array from selection. (Buffersize starts at 0, and grows to your preset buffersizemax as recent choices are added to the buffer.) When you make a choice, you compare it with your bufffersize recent choices. Should you find a match, you select instead the corresponding excluded item.
相反：从选择中排除数组末尾的 buffersize 项。（缓冲区大小从 0 开始，随着最近的选择被添加到缓冲区中，增长到你预设的缓冲区大小最大值。）当你做出选择时，你将它与缓冲区大小最近的选择进行比较。如果找到匹配项，则选择相应的排除项。
Obviously this still has the inefficiency of having to check against every recent choice in the buffer to avoid a match. But it does have the efficiency of avoiding the possible recursion.
显然，这仍然具有必须检查缓冲区中每个最近选择以避免匹配的低效率。但它确实具有避免可能出现的递归的效率。
回答by Mohamad Hamouday
This work like a charm for me without any repeat.
这项工作对我来说就像一种魅力，没有任何重复。
var Random_Value = Pick_Random_Value(Array);
function Pick_Random_Value(IN_Array)
{
if(IN_Array != undefined && IN_Array.length > 0)
{
var Copy_IN_Array = JSON.parse(JSON.stringify(IN_Array));
if((typeof window.Last_Pick_Random_Index !== 'undefined') && (window.Last_Pick_Random_Index !== false))
{
if(Copy_IN_Array[Last_Pick_Random_Index] != undefined)
{
Copy_IN_Array.splice(Last_Pick_Random_Index,1);
}
}
var Return_Value = false;
if(Copy_IN_Array.length > 0)
{
var Random_Key = Math.floor(Math.random() * Copy_IN_Array.length);
Return_Value = Copy_IN_Array[Random_Key];
}
else
{
Return_Value = IN_Array[Last_Pick_Random_Index];
}
window.Last_Pick_Random_Index = IN_Array.indexOf(Return_Value);
if(window.Last_Pick_Random_Index === -1)
{
for (var i = 0; i < IN_Array.length; i++)
{
if (JSON.stringify(IN_Array[i]) === JSON.stringify(Return_Value))
{
window.Last_Pick_Random_Index = i;
break;
}
}
}
return Return_Value;
}
else
{
return false;
}
}
回答by sd6363
I know this is an older question, but I was working through something similar while doing some pre-work for a web development course. In my particular scenario, I wanted to change the color of a box randomly, but not have any consecutive repeats of the same color. This is the solution I came up with. Using a while loop, I was able to achieve the desired result. Hope this helps someone.
我知道这是一个较旧的问题，但我在为 Web 开发课程做一些前期工作时正在研究类似的问题。在我的特定场景中，我想随机改变一个盒子的颜色，但没有任何连续重复的相同颜色。这是我想出的解决方案。使用while循环，我能够达到预期的结果。希望这可以帮助某人。
var colors = ["black","red","yellow","green","blueviolet","brown","coral","orchid","olivedrab","purple"];
function getRandomColor(){
num = Math.floor(Math.random() * 10); // get a random number between 0-9
return colors[num];
}
function randomizeColor(){
currentColor = document.getElementById("box").style.backgroundColor; // got the current color of the box on the page.
randomColor = getRandomColor();
while (randomColor == currentColor){ // if we get the same color as the current color, try again.
randomColor = getRandomColor();
}
document.getElementById("box").style.backgroundColor = randomColor; // change box to new color
}<!DOCTYPE html>
<html>
<head>
<title>Random Color Box</title>
</head>
<body>
<p>Press the buttons to change the box!</p>
<div id="box" style="height:150px; width:150px; background-color:red; margin:25px; opacity:1.0;"></div>
<button id="button" onclick="randomizeColor()">Random Color</button>
<script type="text/javascript" src="javascript.js"></script>
</body>
</html>回答by Robie
//try this:
//试试这个：
var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"];
var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"];
var b = [];
var b = [];
b = shuffle(a).slice(0,5); // this is provided you want 5 numbers.
console.log(b);
b = shuffle(a).slice(0,5); // 前提是您需要 5 个数字。
控制台日志(b);
回答by Shiplu
Try it.
试试看。
function doShuffle(a) {
for (var i = a.length - 1; i > 0; i--) {
var j = Math.floor(Math.random() * (i + 1));
[a[i], a[j]] = [a[j], a[i]];
}
return a;
}
