Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 3 down vote accepted

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
share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.