Algorithm to create permutations for a given alphabet based on a sequence number

Question

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.

Answer 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'])

• OliverS: Very nice. Can't say that I immediately follow but very nice.
• nature1729: This answer will not give word(9, [a,b,c]) = aaa. It will give, ca. This is what your pattern suggests.
• OliverS: Correct. I have edited my question accordingly.
• OliverS: 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.