There's a fairly simple method in javascript to choose a random element from a list using a single instance of Math.random():
Array.prototype.random_choice = function (seed=Math.random()) {
return this[Math.floor(seed * array.length)];
}
I'm looking for a way to choose a randomly ordered collection of k elements of an array, similarly using a single use of Math.random(). Here's what I've got so far:
Array.prototype.random_choice = function(k, seed=Math.random()) {
var array = JSON.parse(JSON.stringify(this)); // deep-copies array
var n = array.length, u = seed, index = 0, choice = [];
while (array.length > Math.max(0, n-k)) {
// index chosen in standard way, as above
index = Math.floor(u*array.length);
// next random number is integer part of u*array.length
u = u*array.length - index;
choice.push(array[index]);
array.splice(index, 1);
}
return choice;
}
It relies on the integer part of some multiple of u being distributed in the same way as u itself, but I know have a good enough understanding of how Math.random() works to know whether this is valid. Furthermore, if my solution is valid, what are its limitations? I assume that the precision of u is finite - which means it won't work for arbitrarily large arrays - but where is the limit?