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

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'])
``````
• Very nice. Can't say that I immediately follow but very nice. – OliverS May 2 '14 at 14:35
• 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