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.
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'])
4