Generate unique random numbers between 1 and 100

Question

How can I generate some unique random numbers between 1 and 100 using JavaScript?

Solution 1

For example: To generate 8 unique random numbers and store them to an array, you can simply do this:

var arr = [];
while(arr.length < 8){
    var r = Math.floor(Math.random() * 100) + 1;
    if(arr.indexOf(r) === -1) arr.push(r);
}
console.log(arr);

Solution 2

1. Populate an array with the numbers 1 through 100.
2. Shuffle it.
3. Take the first 8 elements of the resulting array.

Solution 3

Modern JS Solution using Set (and average case O(n))

const nums = new Set();
while(nums.size !== 8) {
  nums.add(Math.floor(Math.random() * 100) + 1);
}

console.log([...nums]);

Solution 4

Another approach is to generate an 100 items array with ascending numbers and sort it randomly. This leads actually to a really short and (in my opinion) simple snippet.

const numbers = Array(100).fill().map((_, index) => index + 1);
numbers.sort(() => Math.random() - 0.5);
console.log(numbers.slice(0, 8));

Solution 5

Generate permutation of 100 numbers and then choose serially.

Use Knuth Shuffle(aka the Fisher-Yates shuffle) Algorithm.

JavaScript:

  function fisherYates ( myArray,stop_count ) {
  var i = myArray.length;
  if ( i == 0 ) return false;
  int c = 0;
  while ( --i ) {
     var j = Math.floor( Math.random() * ( i + 1 ) );
     var tempi = myArray[i];
     var tempj = myArray[j];
     myArray[i] = tempj;
     myArray[j] = tempi;

     // Edited thanks to Frerich Raabe
     c++;
     if(c == stop_count)return;

   }
}

CODE COPIED FROM LINK.

EDIT:

Improved code:

function fisherYates(myArray,nb_picks)
{
    for (i = myArray.length-1; i > 1  ; i--)
    {
        var r = Math.floor(Math.random()*i);
        var t = myArray[i];
        myArray[i] = myArray[r];
        myArray[r] = t;
    }

    return myArray.slice(0,nb_picks);
}

Potential problem:

Suppose we have array of 100 numbers {e.g. [1,2,3...100]} and we stop swapping after 8 swaps; then most of the times array will look like {1,2,3,76,5,6,7,8,...numbers here will be shuffled ...10}.

Because every number will be swapped with probability 1/100 so prob. of swapping first 8 numbers is 8/100 whereas prob. of swapping other 92 is 92/100.

But if we run algorithm for full array then we are sure (almost)every entry is swapped.

Otherwise we face a question : which 8 numbers to choose?

View more solutions

Comments

[dotty]

Not really a dupe as this is focusing on javascript.

[Pointy]

@dotty well there's no essential difference between doing this in Javascript and doing it in any other language, but I won't vote to close.

[Josh Stodola]

I won't vote to close either. This is specific enough.

[sje397]

This is different. Picking 8 numbers at random from 100 has an answer more efficient than shuffling, which is not the case when you pick all numbers in the range. The proposed dup specifically calls for picking all numbers in the range.

[Jan]

stackoverflow.com/q/4353830/419436

[Huangism]

There is another cleaner way to do this stackoverflow.com/questions/51898200/…

[Roman Starkov]

Actual code is so much better for such questions than pseudocode ;) (deleted my answer that was pseudocode...)

[Alsciende]

O can be picked ; use var randomnumber=Math.ceil(Math.random()*100)

[dotty]

Doesn't work. Firebugs output was "[84, 10, 68, 14, 55, 85, 44, 55]"

[dotty]

Another test case displayed " [70, 70, 54, 60, 82, 50, 23, 33]"

[adam0101]

Added Alsciende's contribution too

[Alsciende]

Permutation solutions are better because they don't become exponentially worse when the number of elements to pick increase.

[dotty]

This seems a better, and shorter, solution.

[adam0101]

@Alsciende wouldn't it depend on the ratio of numbers being picked to the numbers to pick from? For example, if picking 8 numbers from 1 to 1,000,000 I would think this would work better. If picking 800,000 numbers from 1 to 1,000,000 the Knuth Shuffle would be better suited.

[Frerich Raabe]

This approach is correct but suboptimal: you could stop shuffling after eight swaps, since you need only eight random numbers. The code above swaps the entire array (in this scenario, 100 elements).

[adam0101]

But then your eighth number is random from 1 to 92, not 1 to 100. If you had to pick 90 numbers, your last number would only be picked from 1 to 10, wouldn't it?

[Alsciende]

Yes, that's totally right. Although the permutation solution is only in O(n), so I think that's a fair price for safe reusability.

[Alsciende]

@adam0101 No, because he removes numbers as he picks them. So in step 5, there are only 99 numbers in his array. @belugabob You are not more efficient than Knuth Shuffle. In fact, the splice is probably more expensive than the shuffle (which is perfectly reliable)

[Frerich Raabe]

@adam0101: He's removing the chosen element from the array (see step 4 above), thus avoiding that any elements gets chosen twice. He then uses a lower upper bound for the next random number, simply because the array is shorter.

[Frerich Raabe]

You don't need to shuffle the entire array of 1,000,000 numbers. You only need to swap eight numbers, so that the first eight elements are shuffled.

[Frerich Raabe]

-1: this algorithm is the naive approach; it's very inefficient.

[belugabob]

@Alsciende, Yes - thought that there would be a way of doing this more efficiently using a shuffle, but wasn't completely sure. To to avoid deleting the item from the array, simply copy the last entry from the array (providing it wasn't the one that you picked) into the position which you picked from.

[adam0101]

Wow. Naive seems a bit strong. It may not be the best solution, but it's simple, short, easy to see what's going on, and runs within acceptable operating parameters for what needs to be accomplished. On to the next task. Perfection is great, but 'done' is better than 'perfect'.

[Marcel Korpel]

@Frerich: Although I found some inefficiencies (the for loop could be replaced by i=arr.length; while (i--)), I'd be interested in your solution.

[Alsciende]

See my response for an implementation in js

[Alsciende]

The main issue with adam0101's answer is that you can't build a function out of it. It only works well if the number of picks is vastly inferior to the size of the set.

[Alsciende]

The code could be seriously improved. Return values, side effects and function usage are all really blurry IMO. Maybe if you write a function that answers the original problem exactly, using your fisherYates function, it would be clearer.

[Pratik Deoghare]

Answer updated with improved code. Also, @Frerich Raabe: problem with stopping after eight swaps is mentioned.

[belugabob]

Nice recursive implementation - I've posted an alternative, in my answer, that doesn't use splice, as I feel that this is an avoidable performance hit (Not that the OP had any issues with performance)

[Alsciende]

Your Fisher-Yates algorithm is wrong. r should depend on i. See my anwser: stackoverflow.com/questions/2380019/…

[Alsciende]

Ah! recursion is so much more elegant :P But your solution is nice, avoiding the slice. You could make it nicer by decreasing values.length instead of using maxIndex. I prefer my slick Array#pick method, though. (and don't worry about competition, nobody voted me up :( )

[belugabob]

The reason for not decrementing values.length, is that there is no guarantee that decreasing the length of an array is not done by reallocating memory. Using maxIndex has the same effect, by simply ignoring the last entries in the array, as they become irrelevant.

[Alsciende]

Your solution is clever, but I won't use it in my Array#pick method because I don't want this to have its elements shuffled around when I return it.

[Pratik Deoghare]

Ooops sorry my horrible mistake!! Your implementation is cool. Liked it. +1 . Please let me know if anything else is wrong with it.Thanks.

[Alsciende]

Yes, it's still wrong :) i should start at myArray.length and decrease. As it is now, your first step picks a random index between 0 and 0. Otherwise it's correct, but you should rename the stop_count parameter (e.g. nb_picks) and return myArray.slice(0, nb_picks) instead of manually creating result. Might as well use the standard library, right?

[second]

surely it's more efficient to tweak the code to only do the first 8 shuffles? (and then take the last 8 elements of the semi-shuffled array)

[Pratik Deoghare]

Yes right. Learning a lot from you. :) Please,take a look at it again! Thanks again.

[Alsciende]

Well... Now i is initialized with myArray.length, right? So you can't read myArray[i] (well you can but it's undefined). Either start at length-1 (and change the value of r and stop at 0 instead of 1) or access the element as myArray[i-1]. Also, declare i with var.

[Alsciende]

On second thought: if you start at length-1, you must stop at 1. But if you start at length, you must stop at 2.

[Frerich Raabe]

@The Machine Charmer: Performing just eight swaps is fine. It's a standard optimization and the chances of ending up with '1,2,3,76,5,6,7,8' are extremely small. Unless you have a bug in your algorithm implementation. ;-)

[Frerich Raabe]

@Marcel Korpel: The efficiency problems with this solution are on a higher level; the old (like, over 70 years old!) Fisher-Yates algorithm is both shorter and faster. A few of the other answers here use it.

[Pratik Deoghare]

@Frerich Raabe: There are total 100! and there are 92! permutations with first 8 elements untouched. So there is 92!/100! chance that I end up with [1,2,3,..8] :) Not so good i guess :D

[Alsciende]

i=1 must be included in your loop, and r must be Math.floor(Math.random()*(i+1)) to have a random number in [0,i].

[belugabob]

Which array do you not want to be shuffled, the original 1-100 array or the results? The former shouldn't matter, as it's a working array, and the latter will, by the nature of the code, come out in a random order anyway. Not quite sure that I understand your reasons.

[Alsciende]

The original one. I implemented a generic Array#pick method, which I find useful. This function doesn't know if this is a working array or not. To be generic, it doesn't alter this more than necessary.

[belugabob]

But it still alters it, even if only a little, which is unaviodable when using this technique.

[Alsciende]

Hum it doesn't look like you read my answer at all before commenting... My Array#pick method "removes n random elements from array this and returns them". "removes" being the key word here. Just like Array#splice, Array#pick removes some elements, but leaves the rest of the array untouched.

[belugabob]

I read your answer just fine - if Array#splice removes elements, then the array has been changed - or am I missing something?

[Alsciende]

I said "it doesn't alter this more than necessary". The necessary part is the goal of the function : "removes n random elements from the array and returns them". The unnecessary part is "elements get shuffled around".

[tchrist]

This is how I always do it, too. So if I wanted ten random lines from a file with a bunch of lines in it, I do randlines file | head -10.

[Om Shankar]

@Alsciende. Glad that you noticed. The OP has asked between 1 and 100. But this answer's code includes 0 as well - Math.floor(Math.random()*i);

[surfmuggle]

Upvote because i never saw the run code snippet before

[Oscar Yuandinata]

if I want to make a code (8 random alphanumeric string) for coupons, which has to be unique, how can I do it with Chance.js? note: the coupons will be made on demand, so the number of codes will be indefinite

[Victor Quinn]

@OscarYuandinata that's easy, just do var codes = chance.unique(chance.string, 8) If you need the codes pulled from a particular character pool, you can specify that like this: chance.unique(chance.string, 8, {pool: "abcd1234"}) where abcd1234 can be any characters you want in the pool. See chancejs.com/#string

[Oscar Yuandinata]

@VictorQuinn, sorry i didn't make myself clear. I mean the coupon code will be 8 characters random alphanumeric string, not an array of 8 random alphanumeric string. hahaha..

[Victor Quinn]

Oh @OscarYuandinata that's far easier heh chance.string({ length: 8 }) and if you only want certain characters to appear in that string, chance.string({ pool: 'abcd1234', length: 8 }) which would return a random 8 character string from the characters abcd1234, so for example "2c2c44bc" or "331141cc"

[user391986]

This gives me one value in the array that says undefined every 4-5 runs

[adam0101]

@user391986, I'm not seeing that behavior. What browser are you using? Do you get that result if you click the "Run code snippet" button in my answer?

[user391986]

In Google chrome if I run it 5-10 times in a row I get some undefined values back sometimes

[adam0101]

I can't reproduce it using Chrome. Perhaps it's a browser extension you're using or your implementation.

[kaizer1v]

This is a very slow algorithm, since you are running a for loop to check if a random integer already exists, instead have a tempObject with the key and the value same as the random number to check if that key already exists (as shown in my answer).

[Qian Chen]

There is a chance the function returns a 0 in the array. According to this link: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…, Math.random() Returns a random number between 0 (inclusive) and 1 (exclusive). If the Math.random() accidentally returns 0, the Math.ceil(0) is also 0, though the chance is low.

[TBE]

what will happen if i want 0 to be included? the line min = (min) ? min : 1, will always returns 1. (so 0 will never be selected)

[kaizer1v]

A very good point. :). Thank you, I have made the appropriate change. It will now return even if you pass in a 0.

[arslan]

best solution ever. so simple, worked great for me :)

[arslan]

it works great for a small amount. when I try to generate 1000 numbers, it crashed

[roberto tomás]

I think is is the proper answer, because it maintains the probability distrubtion, which the accepted answer does not

[Michael Geary]

@ElgsQianChen Yes, the use of Math.ceil() with Math.random() is always wrong. Besides the chance of returning 0, it also gives an uneven distribution of values. Math.floor() is the correct function to use for something like this.

[Michael Geary]

I took the liberty of editing the answer to change the incorrect use of Math.ceil() so it uses Math.floor() instead.

[Michael Geary]

@Alsciende Just a note for your other projects, your suggestion of using Math.ceil() was incorrect. See my update to the answer for a correct way to use Math.floor() with Math.random().

[Marcin Król]

For the purity of not assigning anything.

[shinzou]

What if N=10^12? Not very efficient.

[ЯegDwight]

@shinzou what N? There is no N anywhere in the question. Stay on-topic.

[shinzou]

Scaled down questions are trivial, in the real world you don't get nice and constant amounts.

[ЯegDwight]

@shinzou in the real world you wouldn't sort 10^12 numbers using JavaScript. A tirival question calls for a trivial answer. I am not here to solve world hunger. I am well-equipped to do that, but that is not what the question is about.

[Anthony Wieser]

Why is it O(n)? Can't it loop for an arbitrary amount of time?

[Alister]

@AnthonyWieser You're right, worst case. I was implying average case since Set.add is o(1)

[adam0101]

I think this could return 0 like my answer used to before it was changed to use Math.floor(Math.random()*100) + 1

[adamfsk]

For this to work with lower bounds other than 1, shouldn't the initial value of maxIndex be either values.length or max - min?

[Gilad Barner]

This is my favorite answer of them all. Dunno why it got only 6 votes. Elegant and with good complexity (provided sort is implemented well, which I'm sure it is).

[Gilad Barner]

Very cool to discover Set in JS! However, wouldn't this solution cause unnecessary generation of numbers until one fits the requirement of uniqueness, especially in the last iterations, if 8 was closer to 100? Thus I think I prefer the also-elegant answer with sort below.

[Sam Mason]

@robertotomás which distribution is being maintained? the currently accepted answer correctly uses rejection sampling to implement "sampling without replacement" with uniform probability of choosing each number

[NoxFly]

This is the method I'm using for a while, but there's a problem with it, because you'll often get "pseudo randomized arrays" which will already have grouped and sorted items at some parts. But there's a way for improve it.

[1antares1]

My favorite answer!