Generate Unique Number Within Range (0 - X), Keeping a History to Prevent Duplicates

Generate unique number within range (0 - X), keeping a history to prevent duplicates

I wrote this function. It keeps its own array with a history of generated numbers, preventing initial duplicates, continuing to output a random number if all numbers in the range have been outputted once:

// Generates a unique number from a range
// keeps track of generated numbers in a history array
// if all numbers in the range have been returned once, keep outputting random numbers within the range
var UniqueRandom = { NumHistory: new Array(), generate: function(maxNum) {
        var current = Math.round(Math.random()*(maxNum-1));
        if (maxNum > 1 && this.NumHistory.length > 0) {
            if (this.NumHistory.length != maxNum) {
                while($.inArray(current, this.NumHistory) != -1) { current = Math.round(Math.random()*(maxNum-1)); }
                this.NumHistory.push(current);
                return current;
            } else {
                //unique numbers done, continue outputting random numbers, or we could reset the history array (NumHistory = [];)
                return current;
            }
        } else {
            //first time only
            this.NumHistory.push(current);
            return current;
        }
    }
};

Here's a working Fiddle

I hope this is of use to someone!

Edit: as pointed out by Pointy below, it might get slow with a large range (here is a
fiddle, going over a range from 0-1000, which seems to run fine). However; I didn't require a very large range, so perhaps this function is indeed not suited if you look to generate and keep track of an enormous range.

Generate random number within range without repeating numbers in javascript

  for (var i = 0, ar = []; i < 80; i++) {
    ar[i] = i;
  }

  // randomize the array
  ar.sort(function () {
      return Math.random() - 0.5;
  });

// You have array ar with numbers 0 to 79 randomized. Verify

console.log(ar);

// take out elements like this

ar.pop()

run for random numbers and keep state

One approach would be to create an array to store existing selections, push selected elements to an array, check if the array contains the element and if the array storing values .length is greater than or equal to maximum range minus minimum range.

It is not clear from description at Question what should occur once all of the elements in the range have been returned?

var range = [10, 20];var not = [];
function randomRange(range, n) {  if (not.length >= range[1] - range[0]) {    return "all numbers in range used"  }  var curr = [];  var res = [];  for (let i = range[0]; i < range[1]; i++) {    if (!not.some(function(num) {      return i == num    }) && not.length < range[1] - range[0]) {      curr.push(i)    }  }  for (let i = 0; i < n; i++) {    var j = curr.splice(Math.floor(Math.random() * curr.length), 1)[0];    res[i] = not[not.length] = j;  }
  return res.filter(Boolean)}
console.log(randomRange(range, 3));console.log(randomRange(range, 3));console.log(randomRange(range, 3));console.log(randomRange(range, 3));console.log(randomRange(range, 3));

Javascript : Making an random array

function randomArray(n) {

  var array = [];
  for (i = 0; i < n; i++) {
    array[i] = i;
  }
  var newArray = [];
  for (i = 0; i < n; i++) {
    var num = Math.round(Math.random() * (n - i - 1));
    newArray[i] = array[num];
    array.splice(num, 1);
  }
  alert(newArray);
}
randomArray(100);

How to generate an array with not repeating numbers in ES6?

You could take a Set and fill this set until the wanted size.

var numbers = new Set;
while (numbers.size < 6) numbers.add(Math.floor(Math.random() * 53));
console.log(...numbers);

random numbers from a small range without multiple repeats

What you are after isn't a pure uniform distribution, as @Henry said.

To enforce your constraint, I think that the best solution is to include a decay factor into your random number generator. As the sequence of numbers increases, the probability of that number appearing next decreases.

I implemented some prototype code in python 3, since my cpp skills are a bit rusty at the moment, but the basic concept is easily translatable to cpp. Here it is:

def my_random(range: int, iterations: int, decay_rate :float = 2) -> List[int]:
    assert range > 0, "`range` must be a positive non-zero integer"

    if range == 1: 
        return [0] * iterations

    last_num: int = 0
    last_prob: float = 1/range
    
    rand_num_lst: List[int] =  []
    while iterations > 0:
        rnd = random() # generates a random number: 0 <= rnd < 1
        if rnd < last_prob:
            num = last_num
            last_prob /= decay_rate
            
        else:
            # The `int` function is converting the float into integer by 
            #    flooring the number
            num = int( (rnd - last_prob) / (1 - last_prob) * (range - 1) )
            
            if num >= last_num:
                num += 1
            
            last_num = num
            last_prob = 1/range/decay_rate
        
        rand_num_lst.append(num)
        iterations -= 1
        
    return rand_num_lst

Note that in Python3 the default division is float division, meaning that 1/2 = 0.5 instead of 1/2 = 0 as it happened in Python2.

I ran some tests to check the maximum sequence length and if the distribution of numbers generated by this is still uniformly distributed, and it seems to continue to hold those properties:

Running with range = 2 and different decay rates:

decay_rate: 2.00000 max sequence length:  6 number count: {0: 499830, 1: 500170}
decay_rate: 1.50000 max sequence length:  6 number count: {0: 499455, 1: 500545}
decay_rate: 1.25000 max sequence length:  9 number count: {0: 500241, 1: 499759}
decay_rate: 1.12500 max sequence length: 11 number count: {0: 499799, 1: 500201}
decay_rate: 1.06250 max sequence length: 14 number count: {0: 500655, 1: 499345}
decay_rate: 1.03125 max sequence length: 16 number count: {0: 500495, 1: 499505}
decay_rate: 1.01562 max sequence length: 16 number count: {0: 500010, 1: 499990}
decay_rate: 1.00781 max sequence length: 18 number count: {0: 499748, 1: 500252}
decay_rate: 1.00391 max sequence length: 18 number count: {0: 499987, 1: 500013}
decay_rate: 1.00195 max sequence length: 21 number count: {0: 499503, 1: 500497}
decay_rate: 1.00098 max sequence length: 21 number count: {0: 500495, 1: 499505}
decay_rate: 1.00000 max sequence length: 19 number count: {0: 499451, 1: 500549}

Running with range = 5 and different decay rates:

decay_rate: 2.00000 max sequence length:  5 number count: {0: 200314, 1: 199245, 2: 200213, 3: 199962, 4: 200266}
decay_rate: 1.50000 max sequence length:  5 number count: {0: 199372, 1: 199829, 2: 199937, 3: 200527, 4: 200335}
decay_rate: 1.25000 max sequence length:  6 number count: {0: 199373, 1: 199784, 2: 200561, 3: 200062, 4: 200220}
decay_rate: 1.12500 max sequence length:  8 number count: {0: 199752, 1: 199931, 2: 200579, 3: 200287, 4: 199451}
decay_rate: 1.06250 max sequence length:  8 number count: {0: 199280, 1: 200286, 2: 199688, 3: 200446, 4: 200300}
decay_rate: 1.03125 max sequence length:  8 number count: {0: 199577, 1: 199582, 2: 200652, 3: 199870, 4: 200319}
decay_rate: 1.01562 max sequence length:  9 number count: {0: 200442, 1: 199916, 2: 200142, 3: 199729, 4: 199771}
decay_rate: 1.00781 max sequence length:  9 number count: {0: 199784, 1: 200544, 2: 199921, 3: 199557, 4: 200194}
decay_rate: 1.00391 max sequence length:  9 number count: {0: 199920, 1: 199054, 2: 200303, 3: 200833, 4: 199890}
decay_rate: 1.00195 max sequence length:  9 number count: {0: 200011, 1: 200530, 2: 199806, 3: 200321, 4: 199332}
decay_rate: 1.00098 max sequence length: 10 number count: {0: 199741, 1: 199861, 2: 199822, 3: 200081, 4: 200495}
decay_rate: 1.00000 max sequence length:  9 number count: {0: 199717, 1: 199184, 2: 200182, 3: 200891, 4: 200026}

Of course you can explicitely code something like: if the running sequence has a length greater than X, just ignore the number and generate one different than the last random number. Although I'm not sure if this method would continue to be uniformly distributed.

---

Related Topics