CODEWITHSUNDEEP
javascript
Russell
Russell

Reputation: 665

How to efficiently randomly select array item without repeats?

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

Upvotes: 26

Views: 46696

Answers (15)

A Haworth
A Haworth

Reputation: 36512

I can't see that any of the answers here actually answered the question as set, though some of the comments come close.

The question asked that an item not be selected for 5 rounds after it has been selected, but then it should be given a chance to be selected, not given a chance only when all the other 9 items have been selected.

This snippet first randomly shuffles the whole array, then takes 5 items from it into a 'resting array'. It then shuffles the remaining items and chooses the first one.

That item is then put onto the end of the resting array, and the first item in the resting array is put to the back of the actual array, arr.

That way an item gets another chance to be selected after it has 'waited' for 5 goes.

function shuffleArray(array) {
  // This is a version of the Fisher-Knuth shuffle algorithm
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
  return array;
}
const resting = 5; //set to the number that must be chosen after an item has been chosen before that item can be chosen again
const arr = ["Roger", "Russell", "Clyde", "Egbert", "Clare", "Bobbie", "Simon", "Elizabeth", "Ted", "Caroline"];;
const len = shuffleArray(arr).length;
var restingArr = [];
for (let i = 0; i < resting; i++) {
  restingArr.push(arr.pop());
}
for (let i = 0; i < 200; i++) {
  const derestedItem = restingArr.shift();
  const chosenItem = shuffleArray(arr).shift();
  restingArr.push(chosenItem);
  arr.push(derestedItem);
  console.log(chosenItem);
}

Upvotes: 0

Andrew Parks
Andrew Parks

Reputation: 8087

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)

Upvotes: 1

smakateer
smakateer

Reputation: 556

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

Upvotes: 14

RonH
RonH

Reputation: 514

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
}

Upvotes: 0

Stephen Saucier
Stephen Saucier

Reputation: 2087

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

Upvotes: 2

sd6363
sd6363

Reputation: 11

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>

Upvotes: 1

Maneesh pandey
Maneesh pandey

Reputation: 1

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

Upvotes: 0

Johann
Johann

Reputation: 29867

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

Upvotes: 0

Shiplu
Shiplu

Reputation: 516

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

Upvotes: -1

Robie
Robie

Reputation: 110

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

Upvotes: -2

Mohamad Hamouday
Mohamad Hamouday

Reputation: 2753

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

Upvotes: 0

Mysha
Mysha

Reputation: 1

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.

Upvotes: 0

zs2020
zs2020

Reputation: 54524

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

Upvotes: 4

Lex Podgorny
Lex Podgorny

Reputation: 2930

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

Upvotes: 1

maerics
maerics

Reputation: 156434

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.

Upvotes: 51

Related Questions