Non-Repetitive Random Number

Unique (non-repeating) random numbers in O(1)?

Initialize an array of 1001 integers with the values 0-1000 and set a variable, max, to the current max index of the array (starting with 1000). Pick a random number, r, between 0 and max, swap the number at the position r with the number at position max and return the number now at position max. Decrement max by 1 and continue. When max is 0, set max back to the size of the array - 1 and start again without the need to reinitialize the array.

Update:
Although I came up with this method on my own when I answered the question, after some research I realize this is a modified version of Fisher-Yates known as Durstenfeld-Fisher-Yates or Knuth-Fisher-Yates. Since the description may be a little difficult to follow, I have provided an example below (using 11 elements instead of 1001):

Array starts off with 11 elements initialized to array[n] = n, max starts off at 10:

+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
+--+--+--+--+--+--+--+--+--+--+--+
^
max

At each iteration, a random number r is selected between 0 and max, array[r] and array[max] are swapped, the new array[max] is returned, and max is decremented:

max = 10, r = 3
+--------------------+
v v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 7| 8| 9| 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 9, r = 7
+-----+
v v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 9| 8| 7: 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 8, r = 1
+--------------------+
v v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 5| 6| 9| 1: 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 7, r = 5
+-----+
v v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 9| 6| 5: 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

...

After 11 iterations, all numbers in the array have been selected, max == 0, and the array elements are shuffled:

+--+--+--+--+--+--+--+--+--+--+--+
| 4|10| 8| 6| 2| 0| 9| 5| 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

At this point, max can be reset to 10 and the process can continue.

Generate a non-repeating random number in JavaScript

You have 2 mistakes, oné is the array inside the function this cleared for each try, and then there is wrong logic ending up in an infinite loop.

const usedIndexes = [];    
function getUniqueRandomNumber(x) {
const index = Math.floor(Math.random() * (x));
if (usedIndexes.includes(index)) {
return this.getUniqueRandomNumber(x);
} else {
console.log(index);
usedIndexes.push(index);
return index;
}
}

Also, I would think about using Set, in this situation instead of the array.

const usedIndexes = new Set();    
function getUniqueRandomNumber(max, min = 0) {
const newNumber = Math.floor(Math.random() * (max - min) + min);
if (usedIndexes.has(newNumber)) {
return this.getUniqueRandomNumber(max, min);
} else {
usedIndexes.add(newNumber);
return newNumber;
}
}

I have also edited variables names to better reflect their actual use and added a minimum for a random number.

Non-repetitive random number in numpy

numpy.random.Generator.choice offers a replace argument to sample without replacement:

from numpy.random import default_rng

rng = default_rng()
numbers = rng.choice(20, size=10, replace=False)

If you're on a pre-1.17 NumPy, without the Generator API, you can use random.sample() from the standard library:

print(random.sample(range(20), 10))

You can also use numpy.random.shuffle() and slicing, but this will be less efficient:

a = numpy.arange(20)
numpy.random.shuffle(a)
print a[:10]

There's also a replace argument in the legacy numpy.random.choice function, but this argument was implemented inefficiently and then left inefficient due to random number stream stability guarantees, so its use isn't recommended. (It basically does the shuffle-and-slice thing internally.)

Some timings:

import timeit
print("when output size/k is large, np.random.default_rng().choice() is far far quicker, even when including time taken to create np.random.default_rng()")
print(1, timeit.timeit("rng.choice(a=10**5, size=10**4, replace=False, shuffle=False)", setup="import numpy as np; rng=np.random.default_rng()", number=10**3)) #0.16003450006246567
print(2, timeit.timeit("np.random.default_rng().choice(a=10**5, size=10**4, replace=False, shuffle=False)", setup="import numpy as np", number=10**3)) #0.19915290002245456

print(3, timeit.timeit("random.sample( population=range(10**5), k=10**4)", setup="import random", number=10**3)) #5.115292700007558

print("when output size/k is very small, random.sample() is quicker")
print(4, timeit.timeit("rng.choice(a=10**5, size=10**1, replace=False, shuffle=False)", setup="import numpy as np; rng=np.random.default_rng()", number=10**3)) #0.01609779999125749
print(5, timeit.timeit("random.sample( population=range(10**5), k=10**1)", setup="import random", number=10**3)) #0.008387799956835806

So numpy.random.Generator.choice is what you usually want to go for, except for very small output size/k.

Java generating non-repeating random numbers

Integer[] arr = {...};
Collections.shuffle(Arrays.asList(arr));

For example:

public static void main(String[] args) {
Integer[] arr = new Integer[1000];
for (int i = 0; i < arr.length; i++) {
arr[i] = i;
}
Collections.shuffle(Arrays.asList(arr));
System.out.println(Arrays.toString(arr));

}

How do I create a list of random numbers without duplicates?

This will return a list of 10 numbers selected from the range 0 to 99, without duplicates.

import random
random.sample(range(100), 10)

Generating non-repeating random numbers in JS

If I understand right then you're just looking for a permutation (i.e. the numbers randomised with no repeats) of the numbers 1-10?
Maybe try generating a randomised list of those numbers, once, at the start, and then just working your way through those?

This will calculate a random permutation of the numbers in nums:

var nums = [1,2,3,4,5,6,7,8,9,10],
ranNums = [],
i = nums.length,
j = 0;

while (i--) {
j = Math.floor(Math.random() * (i+1));
ranNums.push(nums[j]);
nums.splice(j,1);
}

So, for example, if you were looking for random numbers between 1 - 20 that were also even, then you could use:

nums = [2,4,6,8,10,12,14,16,18,20];

Then just read through ranNums in order to recall the random numbers.

This runs no risk of it taking increasingly longer to find unused numbers, as you were finding in your approach.

EDIT: After reading this and running a test on jsperf, it seems like a much better way of doing this is a Fisher–Yates Shuffle:

function shuffle(array) {
var i = array.length,
j = 0,
temp;

while (i--) {

j = Math.floor(Math.random() * (i+1));

// swap randomly chosen element with current element
temp = array[i];
array[i] = array[j];
array[j] = temp;

}

return array;
}

var ranNums = shuffle([1,2,3,4,5,6,7,8,9,10]);

Basically, it's more efficient by avoiding the use of 'expensive' array operations.

BONUS EDIT: Another possibility is using generators (assuming you have support):

function* shuffle(array) {

var i = array.length;

while (i--) {
yield array.splice(Math.floor(Math.random() * (i+1)), 1)[0];
}

}

Then to use:

var ranNums = shuffle([1,2,3,4,5,6,7,8,9,10]);

ranNums.next().value; // first random number from array
ranNums.next().value; // second random number from array
ranNums.next().value; // etc.

where ranNums.next().value will eventually evaluate to undefined once you've run through all the elements in the shuffled array.

Overall this won't be as efficient as the Fisher–Yates Shuffle because you're still splice-ing an array. But the difference is that you're now doing that work only when you need it rather than doing it all upfront, so depending upon your use case, this might be better.



Related Topics



Leave a reply



Submit