Finding a bijective function from integer to words

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.

-
Looks to me that you've already precisely defined the function you want. What more do you need/want? (You might want to shift the table down a step to make room for the empty word, though). –  Henning Makholm Jul 19 '12 at 11:21
I am looking for an explicit definition of f(n) to compute f for an arbitrary n without enumerating recursively. I#ve updated my question accordingly. –  Heinrich Jul 19 '12 at 11:34

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

-
THanks, that does the job. Is there a reverse function? –  Heinrich Jul 22 '12 at 8:41
@Heinrich - I've renamed the function n_to_word, and added an implementation of the inverse function word_to_n. –  r.e.s. Jul 22 '12 at 14:53
Just awesome ... ! –  Heinrich Jul 22 '12 at 15:16

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.

-