# (Efficiently) Generate Unique Random Numbers [duplicate]

Sorry my terminology is somewhat limited so I'll have to use more words to explain what I mean.

In games that require critical hits, I've heard it's not good to generate a random number but instead one should randomly pick a number from a list of possibilities then exclude that number from the next picking. This way, the dev is given more control over the player's experience.

To do this, I've been thinking somewhere along the lines of generating a random number then excluding that number from the next generation. In C#, how can I exclude a number from a random number generation? I don't think that using a while loop to continually check for another number if the currently generated one is excluded is a very efficient method, especially when most of the numbers have been excluded. Is there a built-in method to do this or some clever way to implement it?

Not: I need upwards of 100 numbers to possibly generate so hard-coding it would be tedious.

• Sorry for posting a duplicate question. I suppose it's not needed anymore since I have my answer and it's already been said before. Commented Mar 28, 2015 at 19:21

That sounds really odd to me. This might sound like a good idea if you've got some bad/biased RNG. Another possible use case would be some game with random loot where you'd like to guarantee your player to get some special drop once every x tries rather than having a very bad streak.

However, for your own use case this doesn't sound very useful at all, considering you'll still pick your random number, which influences the number you pick.

In short: If you want no duplicates in the results (e.g. pulling random cards from a deck), then use such an approach. But for pure randomness, e.g. critical hits, this sounds counter-intuitive, especially when you care about performance.

Either way, to implement something like this you could just use a container (again: I don't think this is a good idea):

Random rnd = new Random();

List<int> myList(100);
for (int i = 0; i < 100; ++i)
myList.Item[i] = i; // Or set whatever numbers you need, like card IDs

// Now to pick a random element and remove it:
int random_index = rnd.Next(0, myList.Count);
int random_element = myList.Item[random_index];
myList.RemoveAt(random_index);

I can see why you would want to do that, if the random number was a key seed to a sequence, having the same number twice would create the same sequence.

You could create a table to use as your randoms at program start time, then check it for duplicates, and replace with another random till every number is unique.

If you add all the numbers to a map while generating, you also could tell if some number was already added earlier by the key already being in the map. Maps use binary trees for lookup so it would be pretty fast.

Although if pregenerating the table at start time, a second pass also at start time would be faster while doing lookups.

thinking about it, you could also put numbers 1 to 1000 in a table, then just scramble the order. then go from start to end, and you would have 1000 unique randoms, although you would have to re scramble every 1000 calls to keep from same sequence repeating.

Count from 0 to 1000 in that loop Add Count number before index at rand() % currentTableSize would also create a table of 0 to 1000 scrambled numbers. and table would have zero at end, zero terminated table :)

• Thanks for the idea. This is what I'm going to implement. Commented Mar 28, 2015 at 19:20