How to efficiently randomly select array item without repeats?

Question

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

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.

I have two questions:

1. Is it correct to say this is a "recursive function"?

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

Answer 1

I like commenter @YuriyGalanter's idea of choosing items randomly until all are taken and only then repeating, so here's an 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 2

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 () {
    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.

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

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

Answer 3

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

The function shuffle is implemented in uniformly distributed way so the probability of repetition will be low if the 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

The simplest way to shuffle an array:

['aaa', 'bbb', 'ccc'].sort(() => 0.5 - Math.random())

To access, save the randomized array and either:

1. Keep track of the index you're on & just access the value there, incr/decrementing the index as you wish, or
2. Just .pop() when you want a value

Answer 5

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.

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 6

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.

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>

Answer 7

The standard approach to shuffling is called a Fisher–Yates shuffle. It is fair as long as the random number generator is fair.

It works by randomly removing items from a copy of the unshuffled array until there are none left.

let arr = [1,2,3,4,5,6,7]

let shuffled = arr.reduce(([a,b])=>
  (b.push(...a.splice(Math.random()*a.length|0, 1)), [a,b]),[[...arr],[]])[1]

console.log(shuffled)

Answer 8

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.

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.

Answer 9

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

Answer 10

The selected solution is fine but if you don't want to mess up your array's order, use this solution:

Create an array that contains the indexes of the array used to hold the data you want to randomly select from. Then randomly pick an item from this index array and use its stored value to retrieve the item from the data array. Then remove the index item so that the array of indexes continues to get smaller.

Something like this:

let items = ["red", "blue", "yellow"];
let randomItems = [];
let arrayIndexes =  [...Array(items.length).keys()];

let totalItems = items.length;


for (let i = 0; i < totalItems; i++) {
    let item;

    let mapIndex = Math.floor(Math.random() * (arrayIndexes.length - 1));
    let index = arrayIndexes[mapIndex];
    item = items[index];
    arrayIndexes.splice(mapIndex, 1);

    if ((i === (totalItems - 1)) && (arrayIndexes.length === 0)) {
        // If you choose to set totalItems to a value larger than your dataset,
        // this will re-initialize your array indexes, but you will end up with
        // duplicates in your results. If you don't want duplicates, just make
        // sure totalItems is set to items.length.

        arrayIndexes = [...Array(items.length).keys()];
    }


    randomItems.push(item);
}

Answer 11

var a = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", 
"Elizabeth", "Ted", "Caroline","Brezza","Elephant","Jack","Virat"];    
let b=[a[Math.floor(Math.random() * a.length)]];

for(let i=1; i<=12; i++){
  let t = a[Math.floor(Math.random() * a.length)];
  const n = b.indexOf(t);
   if (n >= 0) {
      b = b.filter((it, i) => it !== t);
    } else {
     b = [...b, t];
    } 
      if(b.length === 12 ){
         break;
       }else{
         if(i === 12){
             i--;
         }
      }
   }

Answer 12

Like the most accepted answer, my solution does not implement the OP's reference to 'the 5 most recent choices' but is instead simply 'choosing items randomly until all are taken and only then repeating'. This solution is not recursive, and there is no chance that it will 'keep looping for a long time before finding a unique name'. It takes advantage of the filter() function and thus avoids the use of a for loop. I believe it is efficient from the perspective of syntactical succinctness.

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

const chooseName = () => {
  let name = b[Math.floor(Math.random() * b.length)]
  b = b.filter((v) => v !== name)
  if (b.length === 0) {
    b = a
  }
  return name
}

Answer 13

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

Answer 14

//try this:

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

var b = [];

b = shuffle(a).slice(0,5); // this is provided you want 5 numbers.
console.log(b);