What is the best way to create a random int list without repetition ?

Question

Currently the best way I have in mind is :

-Creating an empty list
-Doing a for loop
-Generating a random integer here
-Doing a while loop, while the random number is already in the list, we generate an other one
-Put the new integer in the list

Is there a quicker solution ? Because when we want a list of values between 0 and 100 or so, and we want a list with close to 100 elements, it will be quite unoptimized...

Have a good day 🙂

Answer 1

If you know you want a list of unique values that range from 0 to 100 and that list will be close to 100 elements, you will essentially end up with a mixed list of numbers from 0 to 100 anyway. So, why not start with a list of 101 elements consisting of the numbers 0 through 100. Then you can make a single pass over that list doing random indexes to swap values in order to shuffle the list (or use a built-in function/method depending on language and structure used). Then you can simply take a slice of the desired length from that list. This should result in a time complexity of O(n) (depending on what other functions/methods you use with it).

Answer 2

I know about the sample function in python, but I'd like to program one all by myself, so as I can make it in different languages.

By starting with the last index, and generating a random number between the first index and the last one, i think we have the same problem, when we have a wide enough interval at the end...

Answer 3

I think, your way is a good way to generate random integers not repetitive. I'm thinking but I couldn't find any way for a different solution of this problem.
:)
Good luck, happy coding!

Answer 4

So we should separate the problem in 2 :
The algorithm I proposed for a list whose size is small compared to the interval, and an other one for the others.
Anyway, we cannot have better than a O(n) for that 😁

Answer 5

What language do you want to use? In python you can use the sample function of the random module.
https://www.geeksforgeeks.org/python-random-sample-function/

Answer 6

random(0,100);
rect(100,200,100,100)

There a random function in p5js also