Finding a bijective function from integer to words

Question

I need to find a function to enumerate the ordered list of sequential words based on a charset. Let me give you an example.

If the charset is "abc", the function to be found "f" should compute the following:

f(0) =    a
f(1) =    b
f(2) =    c
f(3) =   aa
f(4) =   ab
f(5) =   ac
f(6) =   ba
f(7) =   bb
f(8) =   bb
f(9) =   ca
f(10) =  cb
f(11) =  cc
f(12) = aaa
...

It is important to note that "aaa" is different from "aa" or "aaaa". This is why I found it difficult to represent abc as a number system to the base 3.

I am looking for an explicit definition of f(n) to compute f for an arbitrary n without enumerating recursively.

Answer 1

Your function is a version of bijective numeration. In particular, your $f(n)$ is the ($n+1$)th word in the shortlex ordering of all words on the given alphabet. (The $n+1$ is due to your omission of the empty word.) Here's an implementation (in Sage), which is essentially the algorithm given on the page at the first link above, adapted to use an arbitrary $k$-character alphabet rather than the usual digits {1, 2, ..., $k$}:

def number_to_word(n, alphabet):
    """
    return the nth word (n >= 0) 
    in the shortlex ordering of words on the given alphabet string
    """
    k = len(alphabet)
    word = ''
    while n != 0:
        q = ceil(n/k) - 1
        a = n - q*k
        word = alphabet[a-1] + word
        n = q
    return word

Here's an implementation of the inverse of that function:

def word_to_number(w, alphabet):
    """
    return the number n such that w is the nth word
    in the shortlex ordering of words on the given alphabet string 
    """
    k = len(alphabet)
    n = q = 0
    for c in w[::-1]:
        p = alphabet.index(c) + 1
        n = n + p*(k^q)
        q = q + 1
    return n

For example

for n in [0..15]:
    s = number_to_word(n+1,'abc')
    t = word_to_number(s,'abc')-1
    print '%d --> %s --> %d'%(n,s,t)

produces

0 --> a --> 0
1 --> b --> 1
2 --> c --> 2
3 --> aa --> 3
4 --> ab --> 4
5 --> ac --> 5
6 --> ba --> 6
7 --> bb --> 7
8 --> bc --> 8
9 --> ca --> 9
10 --> cb --> 10
11 --> cc --> 11
12 --> aaa --> 12
13 --> aab --> 13
14 --> aac --> 14
15 --> aba --> 15

Answer 2

If the alphabet contains $\sigma\ge 2$ symbols, then the word consisting of $n$ as has $\sum_{i=1}^{n-1} \sigma^i = \frac{\sigma^n-1}{\sigma-1}-1$ words in front of it. Therefore you have $f(\frac{\sigma^n-1}{\sigma-1}-1)={\tt a}^n$. (The minus one is because you don't encode the empty word).

For a word with letters other than a, interpret it as a numeral in base $\sigma$ to find the distance from the pure a word of the same length, and add it to the index.