title: Algorithm for Gift Card Codes
body: <p><a href="https://stackoverflow.com/questions/1926206/human-readable-guid">I recently posted this question</a> about codes for a gift-card-like voucher that users can redeem online.  I wanted to find the best tradeoff between large keyspace, low guessability, and human readability.  Now that I'm into implementation I realize I've got another problem altogether, more of an algorithmic challenge.</p>
  
  <p>Let's assume I adopt some code format - say 10 characters from A to Z for simplicity, and I start generating vouchers.  What is the correct algorithm to do this?!</p>
  
  <p>My first approach is to number all possible codes from 0 to 308,915,776, then start generating random numbers in that range.  This obviously has a big problem though - I have to check my random number against all previously generated voucher codes and if it collides with an existing one I'll have to discard the code and try another.  As the system accumulates more data it will slow down.  At the extreme when there is only one code left it will be nearly impossible for the system to guess it correctly.</p>
  
  <p>I could pre-generate all codes and shuffle them, then consume them in order.  But this means I have to store many codes, and in fact my keyspace is bigger than the one i described, so we're talking about a very large amount of data.  So that's also not too desirable.</p>
  
  <p>So this leaves me with using the codes sequentially.  I do not want guessable voucher codes though.  The user who buys voucher "AAAAAAAAAY" should not have a good chance of getting another valid code if they type in "AAAAAAAAAZ".</p>
  
  <p>I can shuffle my alphabet and my positions so that instead of</p>
  
  <p>'ABCDEFGHIJKLMNOPQRSTUVWXYZ' i use</p>
  
  <p>'LYFZTGKBNDRAPWEOXQHVJSUMIC'</p>
  
  <p>and so that instead of positions</p>
  
  <p>9 8 7 6 5 4 3 2 1 0
  the positions are</p>
  
  <p>1 8 0 7 5 4 3 9 2 6</p>
  
  <p>Using this logic, given the code</p>
  
  <p>LNWHDTECMA</p>
  
  <p>the next code would be</p>
  
  <p>LNEHDTECMA</p>
  
  <p>This is definitely way less guessable.  But they're still only one character off from each other, and given just two of these vouchers you would know which position is incrementing, and you would have a 90% chance of getting the next code in 24 guesses or less.</p>
  
  <p>My "escape hatch" is to ditch all this and go with GUIDs.  They have more characters than I wanted my users to have to type in, and contain similar characters like I/1 and O/0, but they magically make all of the above headaches go away.  Still, I'm having fun thinking about this, maybe you are too. I'd love to hear some alternate suggestions.  What have you got?</p>
  
  <p>Thanks!</p>