How to make Math.random not repeat same numbers

Hi!
I was trying to make an app and I need to make it show 4 random items from an array but the problem is that with Math.random there’s a possibility to have the same item twice or more times. Does anyone know how to solve this?

1 Like

Hello~!

I would approach this by creating a variable to hold the previously generated value, comparing the current value, and if they are the same regenerate.

I have added an example for you. I think what you are interested in is the haveIt array, the !haveIt.includes(value) line and the recursive call.

let haveIt = [];

function generateUniqueRandom(maxNr) {
    //Generate random number
    let random = (Math.random() * maxNr).toFixed();

    //Coerce to number by boxing
    random = Number(random);

    if(!haveIt.includes(random)) {
        haveIt.push(random);
        return random;
    } else {
        if(haveIt.length < maxNr) {
          //Recursively generate number
         return  generateUniqueRandom(maxNr);
        } else {
          console.log('No more numbers available.')
          return false;
        }
    }
}


console.log(generateUniqueRandom(10));
console.log(generateUniqueRandom(10));
console.log(generateUniqueRandom(10));
console.log(generateUniqueRandom(10));
console.log(generateUniqueRandom(10));

console.log(generateUniqueRandom(10));


console.log(generateUniqueRandom(10));
console.log(generateUniqueRandom(10));
console.log(generateUniqueRandom(10));
console.log(generateUniqueRandom(10));
console.log(generateUniqueRandom(10));
console.log(generateUniqueRandom(10));
console.log(generateUniqueRandom(10));


console.log('Unique random numbers:' ,haveIt);

Output :slight_smile:

1 Like

I assume you don’t want to repeat until you’ve exhausted the array.

There is also a secondary issue that you may/may not care about, that once the array is exhausted, the next value pulled out could repeat the latest value of the previous sequence.

So what you need is a random generator with state: it has to know which values are allowed from a pool of values, it needs to consume that pool, and it needs to store the last value from the pool when the sequence restarts with a full pool.

@nhcarrigan suggestion covers second issue. @GeorgeCrisan suggestion covers first issue (although it uses a global variable and recursion, both of which you probably want to avoid)

What is the context here? It would be helpful to kow that as it dictates tye solution somewhat

2 Likes

simplest way is to remove the used items from array
then no way they can be repeated

var a1 = ['Tom.jpg','Dick2.jpg','Harry.jpg','Bill.jpg'];
var images = a1.slice();
while(images.length){
  rnd = Math.floor(Math.random() * images.length);
  console.log(images[rnd]);
  images[rnd] = '';
  images = images.filter(a=>{return a});
}
console.log(a1);

I think the function I wrote does cover the first issue too. The scope is not really in the context of the problem. Why would you want to avoid recursion when you understand what you are doing?

Eventually, I came up with my own solution but still managed to mess it up so it doesn’t go random anymore but anyways, here’s what I wanted to make

JS isn’t particularly good at recursion (not optimised by the language) and recursive code is normally more difficult to read, so rule of thumb is generally avoid unless it’s necessary. In this case it’s quite elegant but unecessary. That’s why I asked op for the context as well

1 Like

I agree that sometimes there are more than one way of doing same thing.

Simplest way is to shuffle the array then take four values from it. This is the Durstenfeld shuffle algorithm (note that it modifies the array), it’s basically just taken straight from Wikipedia:

export function shuffleArray (arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

If you want four random values then just shuffleArray(myArr).slice(0, 4)

If you want n values without shuffling (this modifies the original array)

function mutableSample (arr, n) {
  const output = [];
  for (let i = 0; i < n; i++) {
    const randomIndex = Math.floor(Math.random() * arr.length);
    output.push(arr[randomIndex]);
    arr.splice(randomIndex, 1);
  }
  return output;
}

If you don’t want to modify the original array, then pass a copy of it to the above function

1 Like

[This is way beyond what’s required, but may/may not be of interest]

To make it fancy, this is where it gets a little more complex. I’ll use the shuffleArray function from above. To spit out an infinite number of non-repeating values:

function* sampleArray (arr) {
  // Start out shuffling the array so it's in random order:
  shuffleArray(arr);
  // I want to keep track of which index I'm at. Once `n` reaches
  // `arr.length`, I know it's time to shuffle the array again:
  let n = 0;

  // Just loop infinitely:
  while (true) {
    // Here is where I shuffle -- the counter goes back to zero at this point.
    if (n === arr.length) {
      shuffleArray(arr);
      n = 0;
    }
    // And I just spit out whatever is at index `n` in the shuffled array:
    yield arr[n];
    // Then move to the next index:
    n++
  }
}

The star on the function keyword (function*) means it’s a generator. That’s used like:

const entryGenerator = sampleArray([1,2,3,4])

Then I can ask for the next value, forever.

entryGenerator.next().value // might return 3
entryGenerator.next().value // might return 1
entryGenerator.next().value // might return 4
entryGenerator.next().value // might return 2
entryGenerator.next().value // might return 4
entryGenerator.next().value // might return 1
entryGenerator.next().value // might return 2
entryGenerator.next().value // might return 3

Which can be encapsulated:

class ArraySampler {
  _generator = undefined;

  constructor (arr) {
    this._generator = sampleArray(arr);
  }

  static init (arr) {
    return new ArraySampler(arr);
  }

  generate () {
    return this._generator.next().value;
  }
}

I use this like this. Initialise it:

const sampler = ArraySampler.init([1,2,3,4])

Then use it:

console.log(sampler.generate())
console.log(sampler.generate())
console.log(sampler.generate())
console.log(sampler.generate())
console.log(sampler.generate())
console.log(sampler.generate())
console.log(sampler.generate())
console.log(sampler.generate())
console.log(sampler.generate())

This is sample output:

1
4
3
2
4
3
1
2
3

I want to have the option of getting a collection of random values at once. I’ll call it a sample. I can integrate this in without closing the generation of numbers – I can ask for sequences of any length and the generator will keep cycling through and shuffling the array to make sure I don’t get repeats:

class ArraySampler {
  _generator = undefined;

  constructor (arr) {
    this._generator = sampleArray(arr);
  }

  static init (arr) {
    return new ArraySampler(arr);
  }

  generate () {
    return this._generator.next().value;
  }

  sample (n) {
    const output = [];
    for (let i = 0; i < n; i++) {
      output.push(this.generate())
    }
    return output;
  }
}

I initialise it exactly the same way, then ask for values like this:

const sampler = ArraySampler.init([1,2,3,4])

console.log(sampler.generate())
console.log(sampler.generate())
console.log(sampler.generate())
console.log(sampler.generate())
console.log(sampler.generate())
console.log(sampler.generate())
console.log(sampler.generate())
console.log(sampler.generate())
console.log(sampler.sample(4))
console.log(sampler.generate())

Note that I’m now getting an array of values halfway through. It still won’t repeat array values until it switches onto starting the cycle again. This is sample output:

1
4
3
2
4
3
1
2
[ 2, 1, 3, 4 ]
3

The 2 then the [2, 1, 3, 4], there’s a repeat (goes 2 then 2). This can be fixed [a bit shoddily] by adjusting the generator to store the last value from the previous cycle and just shuffling until the first value in the new cycle isn’t the same

function* sampleArray (arr) {
  let n = 0;
  let lastValue;

  shuffleArray(arr);

  while (true) {
    if (n === arr.length - 1) {
      lastValue = arr[n];
    }
    if (n === arr.length) {
      do {
        shuffleArray(arr)
      } while (lastValue === arr[0]);
      n = 0;
    }
    yield arr[n];
    n++
  }
}

That could end up shuffling the array a load more times than is necessary, so simpler would be to just switch the first two values in the new cycle:

function* sampleArray (arr) {
  let n = 0;
  let lastValue;

  shuffleArray(arr);

  while (true) {
    if (n === arr.length - 1) {
      lastValue = arr[n];
    }
    if (n === arr.length) {
      shuffleArray(arr)
      if (lastValue === arr[0]) {
        [arr[0], arr[1]] = [arr[1]]
      };
      n = 0;
    }
    yield arr[n];
    n++
  }
}

Now the sequence will never spit out identical values consecutively.


All of this is made under the assumption that the original array has more than one value, so need to handle that case (array has no values or array has only one value).

Also this is impossible to test, so next step would be to replace Math.random() stuff with a seeded random number generator. What this means is that if I give it a “seed” value (could be anything), it will always return the same sequence. That lets me test it.

Also, minor, but I wouldn’t want the generator in the class to be accessible, so I’d make that private. And ideally I’d not want the constructor to be accessible either, so the API is just init, generate and sample, but would need some fiddling to prevent that.

Also, what the array contains and how big it’s likely to be are important – it may be better to generate random indices, rather than shuffling the array and pulling values out of the result – that would only need some minor modification though (I’d be going through a range of integers from 0 to array.length - 1), same principles apply.

As I say, this is purely done as a demonstration – I’ve needed to do this a few times, and this is generally a sane way to do things (lazy sequences).


Full code:

function shuffleArray(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

function* sampleArray (arr) {
  let n = 0;
  let lastValue;

  shuffleArray(arr);

  while (true) {
    if (n === arr.length - 1) {
      lastValue = arr[n];
    }
    if (n === arr.length) {
      shuffleArray(arr)
      if (lastValue === arr[0]) {
        [arr[0], arr[1]] = [arr[1]]
      };
      n = 0;
    }
    yield arr[n];
    n++
  }
}

class ArraySampler {
  _generator = undefined;

  constructor (arr) {
    this._generator = sampleArray(arr);
  }

  static init (arr) {
    return new ArraySampler(arr);
  }

  generate () {
    return this._generator.next().value;
  }

  sample (n) {
    const output = [];
    for (let i = 0; i < n; i++) {
      output.push(this.generate())
    }
    return output;
  }
}
3 Likes

Just hold the visited values in an object and check it at every iteration. You will be storing more data though.

const getUniqueSample = (arr, numOfItems) => {
  const picks = [];

  const visited = {};
  
  for (let i = 0; i < numOfItems; i++) {
    let idx;

    do {
      idx = Math.floor(Math.random() * arr.length);
    } while (!!visited[idx]);

    picks.push(arr[idx]);
    visited[idx] = true;
  }

  return picks;
}

Input:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
4
Output:
[ 8, 5, 7, 4 ]

picks = [ 8 ], visited = { ‘7’: true }
picks = [ 8, 5 ], visited = { ‘4’: true, ‘7’: true }
picks = [ 8, 5, 7 ], visited = { ‘4’: true, ‘6’: true, ‘7’: true }
picks = [ 8, 5, 7, 4 ], visited = { ‘3’: true, ‘4’: true, ‘6’: true, ‘7’: true }

Hope that helps! :slightly_smiling_face:

As the visited array fills this approach will take longer and longer. I’m dubious that the solution is truly constant if you need a large number of values relative to the interval size.

1 Like

You are right. The way I wrote it was misleading. I meant that the look-up part is constant. Obviously the whole function will take more because we are looping through the array. I will edit that.

1 Like

My final solution using Set:
@DanCouper Is there any other simpler, cleaner or more performant way to achieve this?

First parameter (limit - @int) is the max of a random number can be.
Second parameter (totalValues - @int) is the quantity of random unique numbers.

“totalValues” has to be less than or equal “limit” (you can add a check inside of the function if you like).

function uV(limit, totalValues) {
  const uniqueValues = new Set();

  do { uniqueValues.add(Number((Math.random() * limit).toFixed()))  }
    while ( uniqueValues.size < totalValues)

  return Array.from(uniqueValues);
}

Sample:

uV(40,4);


//Output: 
 [ 28, 1,  15,  33 ]

This function returns an array of unique random items
first argument is the array of items second argument
is the number of random items you wish to be returned
the array passed to function is not altered

function randomImages(arr,num){
  var arr = arr.slice(),ret=[];
  while(ret.length<num){
    rnd = Math.floor(Math.random() * arr.length);
    ret.push(arr[rnd]);
    arr[rnd] = '';
    arr = arr.filter(a=>{return a});
  }
  return ret;
}