JavaScript - How to randomly sample items without replacement?

JavaScript

I've tried searching for something like this, but I am not able to find it.

It's a simple idea:

a. Take a random number between 0 to 10.

b. Let's say the random number rolled is a 3.

c. Then, save the number (the 3).

d. Now, take another random number again between 0 to 10, but it can't be the 3, because it has already appeared.

Answers:

Answer

One solution is to generate an array (a "bucket") with all the values you want to pick, in this case all numbers from 0 to 10. Then you pick one randomly from the array and remove it from the bucket. Note that the example below doesn't check if the bucket is empty, so if you call the function below more than 10 times you will get an error.

var bucket = [];

for (var i=0;i<=10;i++) {
    bucket.push(i);
}

function getRandomFromBucket() {
   var randomIndex = Math.floor(Math.random()*bucket.length);
   return bucket.splice(randomIndex, 1)[0];
}

// will pick a random number between 0 and 10, and can be called 10 times
console.log(getRandomFromBucket());
Answer
Var rnd = getRnd();

While(rnd != lastRnd)
  rnd = getRnd();

Where getRnd() is a function that generates your random number.

Actually, you would have to check if your current random number were in an array... And if your list of possible random numbers is small beware of an infinite loop.

Answer

You can use something like this:

/**
* range Get an array of numbers within a range
* @param min {number} Lowest number in array
* @param max {number} Highest number in array
* @param rand {bool} Shuffle array
* @return {array}
*/
range: function( min, max, rand ) {
  var arr = ( new Array( ++max - min ) )
    .join('.').split('.')
    .map(function( v,i ){ return min + i })
  return rand
    ? arr.map(function( v ) { return [ Math.random(), v ] })
       .sort().map(function( v ) { return v[ 1 ] })
    : arr
}

And use it like so:

var arr = range( 1, 10, true )

Now you have an array with 10 numbers from 1 to 10 in random order and never repeated. So next you can do this:

arr.forEach(function( num, i ) { 
  // do something, it will loop 10 times 
  // and num will always be a different number
  // from 1 to 10
});
Answer

Just for fun: derived from @Strilles answer a 'bucket constructor'

function RandomBucket(from,until){
  min = (Number(from) || 0);
  max = (Number(until) || 10)+1;
  this.bucket = String(Array(max-min)).split(',').map(function(i){
     return min++;
  });

  if (!RandomBucket.prototype.get){
   RandomBucket.prototype.get = function(){
      var randomValue = 
        this.bucket.length < 2
        ? this.bucket.shift()
        : this.bucket.splice(Math.floor(Math.random()*this.bucket.length),1);
       return randomValue || 'bucket empty';
      };
  }
}

See JsFiddle for usage example

Answer

using d3:

var bucket = d3.shuffle(d3.range(11));

while(bucket.length) {
  console.log(bucket.pop());
}
Answer

Most of the time I'd stick with the method suggested by the other answers - i.e. create an array of possibilities, create a shuffled version of it, then take the first n values as your sample (all operations that are simple and general and can be implemented immutably).

However this isn't great if the range of possibilities is large compared to how much memory you want to use, or compared to how many random values you want to draw (although @Strilles solution uses the memory, but doesn't draw many random values, so is probably the best even for my usecase below).

A solution along the lines your question seems to suggest could look like this:

// select n integers from the range [from, to] (inclusive at both sides),
// don't use this approach for large values of n
// taking random values from the randomSource as needed
function randomNumbersWithoutReplacement(n, from, to, randomSource = Math.random) {
    const result = [];
    for (let i = 0; i < n; ++i) {
        // i values have already been taken
        // the +1 makes it inclusive
        const rangeWidth = to - from - i + 1

        let value = Math.floor(rangeWidth * randomSource()) + from

        // correct the value compared to the already sampled integers
        for (let j = 0; j < result.length; ++j) {
            if (result[j] <= value) {
                value++
            }
        }

        result.push(value)

        // sorting makes the correction loop simpler
        // (and it's nice to report the result sorted too)
        result.sort((a, b) => a - b)
    }
    return result
}

And why might you want this?

const quantumLottoNumbers = randomNumbersWithoutReplacement(6, 1, 59, quantumRandomSource)

Tags

Recent Questions

Top Questions

Home Tags Terms of Service Privacy Policy DMCA Contact Us

©2020 All rights reserved.