# Making an algorithm that picks a unique random number in fixed set more efficient

I have been working on a project that simulates an online bank. At this point, I'm implementing the code used to create user accounts. Each account will have a sortcode and account number, I have designed an algorithm that can generate a unique number in a range then check if it isn't in the list of account numbers and then add it to the list.

My Issue is that as the number of available account numbers decreases the more times the algorithm will need to generate new numbers which will create exponential overhead. especially when generating 6+ digit long account numbers.

My solution to this problem was after x number of attempts I would run a second operation that would find all missing account numbers in the list and return one at random. This would work but leaves me with the same problem.

Flowchart of my Algorithm Country Code is part of the user registration and each country has it's own selection of sortcodes

so the hierarchy is:

CountryCode > Sortcode > Account Number

The only other solution That I can think of that would remove the overhead issue and give me a unique random number in a set, would be to pre-generate the set of numbers in random order and then pick off the top number until the set is empty. However, I'm not sure where this list would be kept when the application isn't running and I feel generating the numbers at runtime would be more suitable.

If you need any further information I will provide.

• Why can't you just use numbers in sequence: 000001, 000002, etc. If that's not OK, how about using a fast random number generating algorithm as needed? Typically, this has a period $N$, such that if you generate more than $N$ numbers they will repeat, but the period is so long that you won't ever get to $N$. If you don't want to use an off-the-shelf algorithm because it generates 32-bit integers, and you don't want to have to figure out how to map many digits into six digits without duplication, with study one could write a 6-digit linear congruent generator with roughly a $10^6$ period. – Mars Sep 17 '20 at 4:42

## 1 Answer

If you want to generate a list of $$n$$ random codes, from a space of at least $$2n$$ possible codes, then simple rejection sampling is easy and efficient: choose a random code, if it is a repeat throw it away and repeat, otherwise output; and repeat. The running time will be $$O(n)$$. This is the method you have rejected in the question.

If you want to generate a list of $$n$$ random codes, from a space of not much more than $$n$$ random codes, then use a Fisher-Yates shuffle. Create a list of all random codes (0, 1, 2, 3, ...), then randomly permute it using a Fisher-Yates shuffle, then take the first $$n$$ codes in the resulting list. The running time will be $$O(n \log n)$$.