How to write an efficient algorithm that generates a list of unique random numbers?

Question

I'm pretty new to algorithms and am trying to solve a problem that involves generating a list of 5,000 numbers in random order each time it is run. Each number in the list must be unique and be between 1 and 5,000 (inclusive).

function createRandomList() {
  let arr = [];
  while(arr.length < 5000){
    const num = Math.floor(Math.random() * 5000) + 1;
    if(arr.indexOf(num) === -1) arr.push(num);
  }
  console.log(arr);
}

createRandomList()

Here's the solution that I came up with. I wanted to know the Time/Space complexity of this solution. Would it just be O(1) for both space and time because the values are bounded?

Any feedback would be greatly appreciated as well better ways to optimize the solution.

This is definitely not `O(1)`. Simply doing `arr.indexOf` is `O(n)` and you are doing this inside a loop. It looks like you want 5000 items drawn from a population of 0-5000. You are probably better off making a list from 0-5000 and shuffling. — Mark, Jun 13 '21 at 18:16
Just generate your sequence then apply [FIsher-Yates](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle). There are plenty of answers in SO on how to do this. — Rodrigo Rodrigues, Jun 13 '21 at 18:32

danh · Accepted Answer · 2021-06-13T22:15:05.113

1

Keep a sequential list around and shuffle it. Fisher-Yates shuffle in-place is O(n).

Mike Bostock suggests an implementation here.

function shuffle(array) {
  var m = array.length, t, i;

  // While there remain elements to shuffle…
  while (m) {

    // Pick a remaining element…
    i = Math.floor(Math.random() * m--);

    // And swap it with the current element.
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}

const sequence = [1,2,3,4,5,6,7,8,9] // or gen this for any length you choose
let randomNonRepeatingSequence = shuffle(sequence)
console.log(randomNonRepeatingSequence)

edited Jun 13 '21 at 22:15

answered Jun 13 '21 at 19:10

danh

62,181
10
95
136

I wonder why this algorithm should be O(n log n)? It seems more like O(n) to me. It's just iterating once from `n` down to `0`. – derpirscher Jun 13 '21 at 21:23
@derpirscher - I think you're right. The in-place shuffle is O(n). – danh Jun 13 '21 at 22:14

score 0 · Answer 2 · answered Jun 13 '21 at 18:23

0

function createRandomList() {
  let i=0, numbers=[]
  while(i++<5000) numbers.push(i);
  numbers.sort(() => (Math.random() > .5) ? 1 : -1);
  return numbers
}

console.log(createRandomList())

answered Jun 13 '21 at 18:23

Kinglish

23,358
3
22
43

Not so sure about the random return value of the `compareFunction`. Because according to the [docs](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort) the `compareFunction` *"must always return the same value when given a specific pair of elements a and b as its two arguments. If inconsistent results are returned, then the sort order is undefined."* – derpirscher Jun 13 '21 at 18:31
Furthermore, strictly speaking (I know the prng in JavaScript might not be good enough to encounter a real difference) your condition for returning +1 or -1 is biased towards -1, because the range [0, .5] (both inclusive) has more elements (and is therefore at least in a good prng) more likely than the range (.5, 1) (both exclusive). – derpirscher Jun 13 '21 at 18:38
both fair points, and depending on the precision required for this that might matter. However, when you think about it, a consecutive 1-5000 sequence is just as random as a completely unordered sequence. You can flip a coin 1,000,000 times and always get heads (unlikely but possible) but it's still 'random'. As to your first point, I'm not sure what that means - that the resultant array might have less than 5000 items? – Kinglish Jun 13 '21 at 18:45
1

For the first point: no one knows what happens. The results can differ from engine to engine. There may be a crash, there may be no sorting at all, it might create a black hole :) ... No one knows, because it's undefined behaviour. – derpirscher Jun 13 '21 at 19:13
Yes, it might not matter in this case (thus "strictly speaking") but with a biased random function certain permutations may be more likely than others. Yes 10 times heads is possible also with a perfect coin, but extremely unlikely, and it has the same probability as any other sequence. But with a biased coin, it might get more likely, and other sequences get less likely. It might not matter in some cases, but in others (for instance cryptography or lottery) it does. – derpirscher Jun 13 '21 at 19:15

derpirscher · Answer 3 · 2021-06-13T21:26:40.457

Your approach has one big problem: towards the end, it will generate many random numbers which are already contained in your sequence. Consider, you already generated 4999 random numbers. Now for the last one, you only have one possibility left, but you still generate numbers in a range from 1 to 5000. So in average you'll 2500 tries to hit the correct number. Better would be, creating a sequence of your allowed elements and then shuffle this sequence. An easy possibly could be the following.

let arr = [1,2,3,4 ..., 5000]

for (let i = arr.length-1; i > 0; i--){
  let r = Math.floor(Math.random() * (i + 1));
  let x = a[i]; a[i] = a[r]; a[r] = x;
}

How does is work: first you initialize the array with all your allowed values. Then you pick a random index from your array and switch that with the last element of the array. In the next iteration, the range for your random index is decreased by one, and it's switched with the but-last element. And so on and so forth. Once the loop is down to 1, you have a random sequence of your allowed values.

How to write an efficient algorithm that generates a list of unique random numbers?

3 Answers3