How to get a number of random elements from an array?

Question

I am working on 'how to access elements randomly from an array in javascript'. I found many links regarding this. Like: Get random item from JavaScript array

var item = items[Math.floor(Math.random()*items.length)];

But in this, we can choose only one item from the array. If we want more than one elements then how can we achieve this? How can we get more than one element from an array?

Solution 1

Try this non-destructive (and fast) function:

function getRandom(arr, n) {
    var result = new Array(n),
        len = arr.length,
        taken = new Array(len);
    if (n > len)
        throw new RangeError("getRandom: more elements taken than available");
    while (n--) {
        var x = Math.floor(Math.random() * len);
        result[n] = arr[x in taken ? taken[x] : x];
        taken[x] = --len in taken ? taken[len] : len;
    }
    return result;
}

Solution 2

Just two lines :

// Shuffle array
const shuffled = array.sort(() => 0.5 - Math.random());

// Get sub-array of first n elements after shuffled
let selected = shuffled.slice(0, n);

---

DEMO:

Solution 3

There is a one-liner unique solution here

 array.sort(() => Math.random() - Math.random()).slice(0, n)

Solution 4

lodash _.sample and _.sampleSize.

Gets one or n random elements at unique keys from collection up to the size of collection.

_.sample([1, 2, 3, 4]);
// => 2

_.sampleSize([1, 2, 3], 2);
// => [3, 1]
 
_.sampleSize([1, 2, 3], 3);
// => [2, 3, 1]

Solution 5

Getting 5 random items without changing the original array:

const n = 5;
const sample = items
  .map(x => ({ x, r: Math.random() }))
  .sort((a, b) => a.r - b.r)
  .map(a => a.x)
  .slice(0, n);

(Don't use this for big lists)

View more solutions

Comments

[Bergi]

Just execute it multiple times?

[Shyam Dixit]

From this statement can we do this?? Loop generating duplicates.

[Sébastien]

From that exact statement you can't get more than one element.

[Bergi]

Ah, you should've said that you want no duplicates. Then check Unique random numbers in O(1)? and my answer at Generate unique number within range (0 - X), keeping a history to prevent duplicates

[georg]

shuffle the array and get the first N, see stackoverflow.com/q/2450954/989121

[Tibos]

I made a JsPerf to test some of the solutions here. @Bergi's seems to be the best in general, while mine works better if you need many elements from the array. jsperf.com/k-random-elements-from-array

[Shyam Dixit]

In statement items.splice(idx,1) why you use this '1'? splice??

[Tibos]

That depends on the percentage of random items required from the array. If you want 9 random elements from a 10 element array, it will surely be faster to shuffle than to extract 9 random elements one after the other. If the percentage this is useful for is less than 50%, then there are use cases where this solution is the fastest. Otherwise i concede that it is useless :).

[Bergi]

I meant that shuffling 9 elements is faster than shuffling 10 elements. Btw I'm confident that the OP does not want to destroy his input array…

[Tibos]

I don't think i understand how shuffling 9 elements helps in this problem. I am aware that if you want more than half the array you can simply slice-out random elements until you remain with how many you want then shuffle to get a random order. Is there anything i missed? PS: Fixed array destruction, thanks.

[Bergi]

It doesn't have to do anything with "half of". You just need to do as much work as elements you want to get back, you don't need to treat the whole array at any point. Your current code has a complexity of O(n+k) (n elements in the array, you want k of them) while O(k) would be possible (and optimal).

[Tibos]

This is turning into a lengthy discussion :). I think you are mistaken about the complexities. My code has a complexity of O(n). Splicing code (ex:Rory's McCrossan's answer) has a complexity of O(k), but that is not taking into account splicing which can be very expensive (a naive implementation of splicing would get a O(n) complexity for it. I made a JsPerf to test it for a situation i expect shuffling to be better, available here: jsperf.com/k-random-elements-from-array. Feel free to edit it with a better example!

[Bergi]

OK, your code has more like O(2n) which could be reduced to O(n+k) if you'd change the loop to while (counter-- > len-k) and take the last (instead of first) k elements out of it. Indeed splice(i, 1) doesn't have O(1), but a O(k) solution is still possible (see my answer). Space complexity however stays at O(n+k) unfortunately, but could become O(2k) depending on the sparse array implementation.

[Prajeeth Emanuel]

Hey man, I just wanted to say I spent about ten minutes appreciating the beauty of this algorithm.

[unitario]

Very nice! One liner also of course possible: let random = array.sort(() => .5 - Math.random()).slice(0,n)

[asetniop]

There's something strange going on with the randomization in this one - I had the same result show up 6 out of 9 tries (with an n of 8 and an array size of 148). You might think about switching to a Fisher-Yates method; it's what I did and now works much better.

[Ry-]

This takes quadratic time because it does a bad uniqueness check and doesn’t have an equal chance of selecting every item because it sorts with a random comparison.

[Bergi]

@Derek朕會功夫 Ah, clever, that works much better for small samples from large ranges indeed. Especially with using an ES6 Set (which wasn't available in '13 :-/)

[Vlad]

Genius! Elegant, short and simple, fast, using built-in functionality.

[Kurt Peek]

Shyam Dixit, according to the MDN documentation the 1 is the deleteCount indicating the number of old array elements to remove. (Incidentally, I reduced the last two lines to newItems.push(items.splice(idx, 1)[0])).

[Bergi]

@AlexWhite Thanks for the feedback, I can't believe this bug evaded everyone for years. Fixed. You should have posted a comment though, not suggested an edit.

[pomber]

It's nice, but is far from random. The first item has many more chances to get picked than the last one. See here why: stackoverflow.com/a/18650169/1325646

[Joel]

Welcome to SO! When posting answers, it is important to mention how your code works and/or how it solves OP's problem :)

[almathie]

This does not preserve the sort of the original array

[evilReiko]

Good answer! Have a look at my answer, copied your code and added "only unique elements" functionality.

[Yair Levy]

Amazing! if you want to keep the array intact you can just alter the first line like this: const shuffled = [...array].sort(() => 0.5 - Math.random());

[Sampo]

This function can return the same element of sourceArray multiple times.

[cbdeveloper]

@Bergi this is mind bending. Can I be sure that it won't select the same item more than one time? Thanks!

[Bergi]

@cbdev420 Yes, it's just a (partial) fisher-yates shuffle

[Qasim]

Could we have a better explanation of how this works?

[robross0606]

I'm trying to wrap my head around how this implementation would not yield duplicates. The comments seem to indicate that it would and then it wouldn't. But, looking at the code, I don't see how it would prevent duplicates. What am I missing?

[Bergi]

@robross0606 I'm confused by those old comments as well, I've flagged them to be removed. This answer definitely does not produce duplicates (or, only if the input arr did contain some), by keeping track of the indices that already were taken. "Editing the question now would invalidate the answers" refers to other answers, like the one by Laurynas.

[user]

I've posted an optimized version of this code below. Also corrected the wrong random parameter in the second algo in your post. I wonder how many people are using the previous biased version in production, hope nothing critical.

[philk]

while it works it might also be slow for bigger arrays.

[philk]

@Bergi I wonder how a predicate could be worked into that? So that one could say "I don't want to have a particular item to be included in the result array`. And also protect against an infinite loop over len when all selected elements being rejected by the predicate.

[Bergi]

@philk Just don't include that particular item in the array that you pass? getRandom(items.filter(…), …)

[JasonWoof]

This does not get you an even distribution. See robweir.com/blog/2010/02/microsoft-random-browser-ballot.htm‌​l

[disfated]

There's an error in log(k*3, 4) since JS doesn't have the base argument. Should be log(k*3)/log(4)

[disfated]

Also, I see a downside in the part where you reuse pool as a result. Since you truncate pool it cannot be used as a source for sampling any longer and next time you use sample you will have to recreate pool from some source again. Derek's implementation only shuffles the pool, so it can be perfectly reused for sampling without recreating. And I believe this is the most frequent use case.

[MAMY Sébastien]

I realize that the function does not generate all possible random array from a source array. In other world, the result is not as random as it should... any idea of improvement?

[vanowm]

where is _shuffle function?

[vanowm]

What is _? It's not a standard Javascript object.

[Valery]

You are not making sure two items don't get repeated.

[Patrolin]

Results in slightly uneven distribution.

[user]

@disfated, thanks, fixed log in my and Derek's code. As for reusing the pool, just don't enable the destructive option, then the pool argument is shadowed with a copy.

[idleberg]

Also, when the size >= ar.length, the result will be size-1

[Rubek Joshi]

@vanowm It's lodash which is usually imported with the _ alias.

[jeffbRTC]

Neat and concise!

[Jochem Schulenklopper]

@Qasim, the algorithm takes an array of items (line 2) and makes an array of pairs: the original item and a random number (line 3). It then sorts the array of pairs per the random number (line 4). Then it makes a list of simple items again, only using the original item (thus skipping the random number, line 5). Finally, it picks the first n items of the (randomly ordered) array of items (line 6). For a better understanding, read the documentation of functions like map and sort, like in developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/….

[DedaDev]

the op wasn't asking for that

[Martijn Scheffer]

the problem with this method is that it will get increasingly slow, and in the end it could get slower than just removing the elements you pick

[Martijn Scheffer]

please don't use jQuery for this type of code

[Bergi]

@MartijnScheffer No, it doesn't get slower, it gives you n elements in O(n) bounded time

[evilReiko]

@MartijnScheffer the original question was asking for a solution using jQuery

[KeshavDulal]

The jsPerf link seems broken at the moment.

[I wrestled a bear once.]

@KeshavDulal - jsPerf has been offline for a long time. This answer is nearly a decade old.

[João Pimentel Ferreira]

It's nice but CPU intensive for big arrays; why do you need to sort the whole array if you will pick up only few elements?

[Geoffrey Hale]

This is not random!

[joe.kovalski]

This is a simple solution for simple cases, but for large arrays, it's not truly random. I suggest using Fisher-Yates (aka Knuth) Shuffle and then you should cut first N results with the slice.