Populate array with non repeating random numbers

Question

So I have an array called arr.

I want to populate it with four random numbers:

for (var i = 0; i < 4; i++) {
  arr[i] = Math.floor(Math.random() * 10);
}

If that returns an array with values [4, 2, 3, 4]. How do I check for duplicates, and recalculate a random number that doesn't equal any other values that already exist in the array?

Also if there is a better way of accomplishing this, I would love to learn/know that way as well.

Mike 'Pomax' Kamermans · Answer 1 · 2016-05-01T02:45:59.503

3

Also if there is a better way of accomplishing this, I would love to learn/know that way as well.

There is.

If you need unique values, generate a regular sequential array [1,2,3,4] (or however long you need), and then use that to fill a second array, by successively extracting random elements from the first array (thus growing array 2, and shrinking array 1):

var a1 = [];
for (var i=0; i<4; i++) { a1.push(i); }
var a2 = [];
while (a1.length) {
  var pos = Math.random()*a1.length;
  var element = a1.splice(pos, 1)[0];
  a2.push(element);
}
// a2 is now an array with a random permutation of the elements of a1

The splice call removes an subarray starting at position pos with (in this case) 1 element, so a1 gets shorter and shorter, until it's empty, at which point a2 will be a permuted array of unique values.

If we start with a1 = [0,1,2,3] then after this runs a2 can be any of 24 possible sequences, with guaranteed unique values because that's what we started with, just in a randomised order.

edited May 01 '16 at 02:45

answered May 01 '16 at 01:28

Mike 'Pomax' Kamermans

49,297
16
112
153

Hi, I'd just like to point out that this solution isn't very efficient. If you're going to be generating large arrays, this solution takes `O(N^2)` time, whereas the optimal is `O(N)`. – Eric Zhang May 01 '16 at 05:02
that's not a very useful thing to say without links to other solutions already on SO or on the web at large =) Indeed, as an O(n²) algorithm you don't want to use this for long sequences, but "long" is relative; on my computer the numbers are ~10ms for 1000 and ~80ms for 10000, both of which are arguably already so large that you don't want to write your own code, but you just want to use a combinatorics library instead because you're in "arbitrary data" land. – Mike 'Pomax' Kamermans May 01 '16 at 16:10
I believe both LWChris's answer and my own are both `O(N)` algorithms, in contrast to this one, which is `O(N^2)`. The question asked for the actual way it's done, not a library to do it :) – Eric Zhang May 02 '16 at 01:55

score 1 · Answer 2 · answered May 01 '16 at 01:28

1

What you are looking for is a way to take a random sample from an array of the integers [0..9]. You can do this with several algorithms, for example a simple reservoir sampling algorithm.

answered May 01 '16 at 01:28

Eric Zhang

591
6
13

score 1 · Answer 3 · edited May 23 '17 at 10:28

If you want to have an array that contains any amount of numbers from 1 to n in random order, I think the more viable approach is to generate an array with all numbers from 1 to n and then shuffle it as described here.

You can then proceed to splice the array after shuffling to shorten it to the desired length.

Both steps have the complexity of O(1) or O(n), which is far better than testing for every insert or modifying a value pool from which you draw the numbers.

score 0 · Answer 4 · answered May 01 '16 at 01:45

I'd probably make a function for the loop.

function getNumber(arr){
   var num = Math.floor(Math.random() * 10);
   if(arr.indexOf(num) < 0){
      return num;
   } else {
      getNumber(arr);
   };
};

Then you would do:

var arr = [];
for (var i = 0; i < 4; i++) {
  arr[i] = getNumber(arr);
}

Populate array with non repeating random numbers

4 Answers4