I'm working with a client that needs to generate millions of the alphanumeric codes used in magazine scratch-off cards, bottlecap prizes, and so on. They have to be short enough to print on a cap, they want to make sure that ambiguous characters like 1 and I, 0 and O, etc. are not included, and they have to be explicitly stored for future use -- we can't just have an algorithm that determines 'validity' when someone tries to redeem one. Finally, they want to make sure that the codes are randomly distributed inside of a large "code space" so that people can't just guess additional codes by walking through the alphabet.
Are there any pointers towards reasonably efficient algorithms for generating these kinds of code sets? I've scratched a few out on the back of an envelope, but this problem smells like a trap for the unwary.
If you need about 10 million unique keys (for example), the best approach is to pick a key-space that's exponentially bigger, and start randomly generating. Read about the Birthday Paradox -- it's the main thing you should be worried about. If you want 2^n unique and secure keys, make sure there are at least 2^(2 * n) possible values. Here's a rough O(n log n) algorithm:
Pseudocode:
$last = null;
while ($current = getnext()) {
if ($last == $current) {
push($toDelete, $current);
}
$last = $current;
}