Generate short database identifier names from an integer

Question

I wrote the following to generate short database identifier names (e.g. parameters). This isn't a terribly practical requirement and could be fulfilled nearly as well by using base-26, but what seemed like a simple problem became an interesting challenge.

My result doesn't feel very clean, and it has some collisions. I would appreciate performance or elegance suggestions.

Rules: First character must be alphabetic, subsequent must be alphanumeric.

public string intToDatabaseIdentifier(int number)
{
    if(number < 0 || number > 1000000)
        throw new ArgumentOutOfRangeException("number");
    if(number > 25 && number <= 25 + 10) // Skip 0-9 (modified base 36)
        number += 10;
    if(number > 971 && number <= 971 + 360) // Skip 0a-09 (modified base 36)
        number += 360;
    if(number > 35027 && number <= 35027 + 12960) // Skip 0aa-099 (modified base 36)
        number += 12960;
    var stack = new Stack<char>();
    // Base 36, but starting with letters rather than numbers
    const string characters = "abcdefghijklmnopqrstuvwxyz0123456789";
    while(number >= 0) {
        stack.Push(characters[number % 36]);
        number = number / 36 - 1;
    }
    return new string(stack.ToArray());
}

Additional characters (e.g. _, #) can be easily added, but they yield little and make the method less database-agnostic, so I'll stick with alphanumerics.

Results:

a b c d e f g h i j k l m n o p q r s t u v w x y z
aa ab ac ad ae af ag ah ai aj aa ab ac ad ae af ag ah ai aj ak al am an ao
ap aq ar as at au av aw ax ay az a0 a1...

Ideally the output will be as above (without the collisions). The accepted answer in SO works but produces output in an unusual order, e.g. aa ba ca

Answer 1

The trick is to find a formula for where a new place has to be added. In this case the formula is:

$$ d_k = 26*(36^k-1)/35 $$

If n >= d_k then the name of n has at least k+1 digits.

The turnover points are 26, 962, 34658, 1247714, ...

name 24          = y
name 25          = z
name 26          = aa
name 27          = ab

name 960         = z8
name 961         = z9
name 962         = aaa
name 963         = aab

name 34656       = z98
name 34657       = z99
name 34658       = aaaa
name 34659       = aaab

name 1247712     = z998
name 1247713     = z999
name 1247714     = aaaaa
name 1247715     = aaaab

name 44917728    = z9998
name 44917729    = z9999
name 44917730    = aaaaaa
name 44917731    = aaaaab

After finding k, just represent n - d_k as a k+1 digit number base 36.

Some Python code:

theChars = "abcdefghijklmnopqrstuvwxyz0123456789"

# the magic formula:
def dk(k):
  return (26 * (36**k-1)) / 35 

def name(n):
  # find the largest k s.t. dk(k) <= n
  k = 0
  while dk(k) <= n:
    k += 1
  k -= 1
  # take k+1 digits mod 36
  q = n - dk(k)
  digits = ""
  while k >= 0:
    r = q % 36
    q = q / 36
    digits = digits + theChars[r]
    k -= 1
  return digits[::-1]  # shortcut to reverse a string

def testForDuplicates(a,b):
  seen = set()
  for n in xrange(a,b):
    m = name(n)
    if m in seen:
      print "duplicate found at n =", n, ", name:", m
    seen.add(m)

def printRange(a,b):
  for n in xrange(a,b+1):
    print n, " ->", name(n)

printRange(20,30)
printRange(955,965)
printRange(34650,34662)
printRange(1247710,1247720)
printRange(44917727,4491773)

testForDuplicates(0,1000000) # takes about 6 secs