Question

65

Sampling a random subset from an array

rated 0 times [ 68] [ 3] / answers: 1 / hits: 41394 / 12 Years ago, mon, august 13, 2012, 12:00:00

What is a clean way of taking a random sample, without replacement from an array in javascript? So suppose there is an array

x = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

and I want to randomly sample 5 unique values; i.e. generate a random subset of length 5. To generate one random sample one could do something like:

x[Math.floor(Math.random()*x.length)];

But if this is done multiple times, there is a risk of a grabbing the same entry multiple times.

Answers

Only authorized users can answer the question. Please sign in first, or register a free account.

kayap

Add To Favorites

Follow

Total Points: 634

Total Questions: 83

Total Answers: 110

Location: Saudi Arabia

Member since Mon, Sep 5, 2022

2 Years ago

answered 12 Years ago deonkalvinw · Accepted Answer

I suggest shuffling a copy of the array using the Fisher-Yates shuffle and taking a slice:

function getRandomSubarray(arr, size) {

    var shuffled = arr.slice(0), i = arr.length, temp, index;

    while (i--) {

        index = Math.floor((i + 1) * Math.random());

        temp = shuffled[index];

        shuffled[index] = shuffled[i];

        shuffled[i] = temp;

    }

    return shuffled.slice(0, size);

}



var x = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];

var fiveRandomMembers = getRandomSubarray(x, 5);

Note that this will not be the most efficient method for getting a small random subset of a large array because it shuffles the whole array unnecessarily. For better performance you could do a partial shuffle instead:

function getRandomSubarray(arr, size) {

    var shuffled = arr.slice(0), i = arr.length, min = i - size, temp, index;

    while (i-- > min) {

        index = Math.floor((i + 1) * Math.random());

        temp = shuffled[index];

        shuffled[index] = shuffled[i];

        shuffled[i] = temp;

    }

    return shuffled.slice(min);

}