CODEWITHSUNDEEP
algorithmrandom
AlexStack
AlexStack

Reputation: 17381

Random generator without repeated result

I need to put the numbers from low to high in an array randomly.

For example given: low = 10, high = 15 a result like [ 12, 13, 10, 14, 11] is good.

This is a simple algorithm: iterate from low to high and try to fill in the empty slots on an array.

const low = 1000
const high = 1010

const diff = high - low
const arr = new Array(diff)

for (var i = low; i < high; i++) {
  let success = false
  while(!success) {
    const index = Math.floor(Math.random() * diff)
    if (arr[index] === undefined) {
      arr[index] = i
      success = true
    }
    console.log(`${index} was ${success ? 'available' : 'taken'}`)
  }
}

console.log(arr)

The problem is: in the end where most of the elements are filled, it is harder to find an unoccupied slot in the array.

My question is: is there an algorithm that constantly generates unique new numbers until all the numbers are consumed?

Another way to think about it is an algorithm that shuffles an array the most efficient and quickest way.

Upvotes: 0

Views: 106

Answers (3)

Shanu Gupta
Shanu Gupta

Reputation: 3807

For someone looking this in java, just use Collections API.

We have:

Collections.shuffle(yourOriginalArray);

Upvotes: 0

AlexStack
AlexStack

Reputation: 17381

Another implementation of Fisher-Yates Shuffle:

const low = 1000
const high = 1010
const delta = high - low
const arr = [...new Array(delta)]
arr.forEach((value, index, arr) => arr[index] = index + low)

const result = []
while (arr.length > 0) {
  const index = Math.floor(Math.random() * arr.length)
  result.push(arr[index])
  arr.splice(index, 1)
}

console.log(result)

Upvotes: 0

Sani Huttunen
Sani Huttunen

Reputation: 24385

Instead of generating "random" numbers, generate a list of the numbers and shuffle it "randomly" by using something like Fisher-Yates Shuffle:

function getRandomArray(min, max) {
  return shuffle([...Array(max - min).keys()].map(i => i + min));
}

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

  while (m) {

    i = Math.floor(Math.random() * m--);

    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}

var randomArr = getRandomArray(10, 15);
console.log(randomArr);

Upvotes: 4

Related Questions