How to effectively randomly select an array element without repeating?

Question

I know that this question exists in many guises, but I could not find an answer related to my specific problem of efficiency.

I have the code below that works fine.

I have 10 arrays of elements from which I randomly select an element (when I press the enter key). The code stores an array of the 5 most recent selections that cannot be randomly selected (to avoid too many repetitions over time).

If the selectName () function initially selects the name that was used in the last 5, it simply breaks and calls itself again, repeating until it finds a "unique" name.

I have two questions:

• Can this be said to be a "recursive function"?

• I am worried that in theory this could go on for a long time before finding a unique name - is there a better way to do this?

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

Answer 1

Whenever an element is selected, move it to the back of the array and randomly select array.slice(0, -5) from the slice of the original array.

 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 a side effect of the fact that any variables do not match the list of unfair flaw, which they will not consider in the first N calls. If this is a problem for you, perhaps try storing a static variable somewhere to keep track of the size of the fragment used and make the most of it in B (in this case 5). eg.

 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 2

I like the @YuriyGalanter commentator the idea of ​​randomly selecting items until everyone is accepted and only then repeated, so here's the implementation:

 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 3

I recommend you use underscore.js , it will be very simple.

The shuffle function is implemented in a uniformly distributed way, so the probability of repetition will be low if array a contains more data.

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

Answer 4

When you create an instance of Shuffler, give it your array as a parameter. It will create a copy of the array and each time next () is called, it will return a random element from the copy and remove it from the copy array so that there are no repetitions.

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

Answer 5

Instead of randomly choosing from a list of arrays, how to shuffle an array in a random order at the beginning?

Answer 6

Yes, this is recursive, and since it does not reduce the state, which theoretically can go on forever.

I assume that changing the array is unacceptable, since otherwise you could just remove the last options from the array and discard them as a recent selection buffer overflow.

Instead: Exclude buffering elements at the end of the array from the selection. (Buffersize starts at 0 and grows to your predefined buffer max when the latest options are added to the buffer.) When you make a selection, you compare it with your favorite bufffersize options. If you find a match, you select the appropriate excluded item.

Obviously, the need to check every recent selection in the buffer is still ineffective to avoid a match. But it has efficiency that avoids possible recursion.

Answer 7

This work is like charm to me without repetition.

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

Answer 8

I know this is an old question, but I was working on something similar, getting ready for a web development course. In my specific scenario, I wanted to change the color of the block randomly, but not have successive repeats of the same color. This is the solution I came up with. Using the while loop, I was able to achieve the desired result. Hope this helps someone.

 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>