How to generate a list of unique random strings?

Question

How would you generate a list of distinct random strings, where all strings are alphanumeric and have a fixed length?

Answer 1

There are three general solutions to the non-duplicate random number problem:

• If you want a few numbers from a large range then pick one and reject it if it is a duplicate. If the range is large, then this won't cause too many repeated attempts.

• If you want a lot of numbers from a small range, then set out all the numbers in an array and shuffle the array. The Fisher-Yates algorithm is standard for array shuffling. Take the random numbers in sequence from the shuffled array.

• If you want a lot of numbers from a large range then use an appropriately sized encryption algorithm. E.g. for 64 bit numbers use DES and encrypt 0, 1, 2, 3, ... in sequence. The output is guaranteed unique because encryption is reversible. The Hasty Pudding Cipher can be set for any convenient range of numbers.

Answer 2

To expand on rossum's answer:

The Fisher–Yates shuffle is actually quite a versatile algorithm. In particular, you can use it in "on-demand mode", where, whenever you need a new random number, you run one step of the algorithm (Durstenfeld version or equivalent) and output $a[i]$ (where $a$ is the array being shuffled and $i$ is the loop counter).

Also, with a sparse array, you can generate $n$ unique random numbers from any range using $\Theta(n)$ time and space (assuming that storing and retrieving an element takes $\mathrm O(1)$ time and space). Basically, you use the standard Fisher–Yates shuffle, but only physically store those elements of the array $a$ for which $a[i] \ne i$. (In on-demand mode, you also don't need to store the elements that have already been output, since the algorithm won't ever reuse them.)

The rejection technique also needs at least $\Theta(n)$ time and space (since the output values must be stored somehow to let them be rejected), so in that sense it's no better than the Fisher–Yates shuffle even for large domains; however, in some cases it might be simpler to implement. Note, though, that simple implementations using a flat array to store duplicates will usually end up needing $\Omega(n^2)$ time to generate $n$ values. In general, I wouldn't expect an efficient implementation of the rejection method to be significantly less complicated than a comparable implementation of the Fisher–Yates method.

The block cipher method needs only $O(1)$ storage, excluding the output, and may therefore be preferable in some cases. As Gordon Davisson notes in the comments, it cannot be used to generate truly random output — but then, the other methods are also most often used with only pseudorandom input, in which case they have no special advantage there.

Finally, of course, if your domain is large enough (as in larger than $kn^2/2$ possible values, where $n$ is the number of values you want to generate and $k$ is an arbitrary security parameter), you can just pick uniform random values from the domain without worrying about duplicates, knowing that the probability of a collision is less than $1/k$.

Answer 3

We want a list of $n$ distinct random-like non-negative integers less than $m$, obviously with with $n \le m$.

One option is to build a cipher $C$ over the set of non-negative integers less than $m$; select a fixed random key $K$ for that cipher; and construct the desired list as $C_K(i)$ for $0 \le i \lt n$. The rationale is that a good cipher over a set, with a random key, is indistinguishable from a random permutation of this set.

If $m = 2^{128}$, a safe choice for the cipher is AES (with a key size of 128, 192 or 256 bit depending on the paranoia required security level). If $m = 2^{64}$, 3DES is fine (perhaps with the restriction $n \lt m-1$, if we could find an efficient way to predict the butlast two values from the previous $2^{64}-2$ and the fact that 3DES is an even permutation, which BTW is an interesting problem).

For other $m$, we can build a custom cipher. See John Black and Phillip Rogaway: Ciphers with Arbitrary Finite Domains; or, especially for moderate $m$ and $n$ approaching $m$, Louis Granboulan and Thomas Pornin: Perfect Block Ciphers With Small Blocks.