1

I would like to have a function that will create a word (always the same word) for a given sequence number based on a given alphabet.

word(0, [a,b,c]) = a
word(1, [a,b,c]) = b
word(2, [a,b,c]) = c
word(3, [a,b,c]) = aa
word(4, [a,b,c]) = ab
word(5, [a,b,c]) = ac
word(6, [a,b,c]) = ba
word(7, [a,b,c]) = bb
word(8, [a,b,c]) = bc
word(9, [a,b,c]) = ca
...

I was able to recursively create all permutations of a given length but starting with length 5 it already gets quite big in memory.

1

Let n be the size of alphabet (here 3).

Now ath number in the above scheme will lie between

0 <= a < n or 0 + n <= a < 0 + n + n*n or ...

0 + n + n^2 + ... + n^m <= a < 0 + n + n^2 + ... + n^(m+1)

Solving for m we get,

m = int(log(a(n-1)/n + 1)/log(n))

Here it is,

m = int(log(2*a/3 + 1)/log(3))

Now we subtract n*(n^m-1)/(n-1) from a getting b. b will be a number of (m+1) places in a number system with radix n.

I have put a small python code for it like this:

from math import*

f = lambda a : int(log(2*a/3.0 + 1.0)/ log(3))

alpha = ['a','b','c']


def get_repr(a):
    m = f(a)
    if m == 0:
        b = a
    else:
        trunc = 3*((3**m)-1)/(2)
        b = a - trunc
    s = ''
    for q in range(0, m+1):
        s =   alpha[(b%3)] + s
        b /= 3
    return s


print get_repr(8)

EDIT: We can avoid jargon of logarithm and all, and can use the following:

def word(a, alphabet):
    k = 1
    N = len(alphabet)
    n = N
    while True:
        if a < n:
            break
        else:
            a = a - n
            n = n*N
            k = k + 1
    s = ''
    for q in range(0, k):
        s =   alphabet[(a%N)] + s
        a /= N
    return s


print word(1, ['a','b','c'])
  • Very nice. Can't say that I immediately follow but very nice. – OliverS May 2 '14 at 14:35
  • 1
    This answer will not give word(9, [a,b,c]) = aaa. It will give, ca. This is what your pattern suggests. – nature1729 May 2 '14 at 14:38
  • Correct. I have edited my question accordingly. – OliverS May 2 '14 at 14:54
  • I also thought about number systems but couldn't get past the problem that the first item would be the neutral element and 00 would never be created. – OliverS May 2 '14 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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