current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 1 down vote favorite
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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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'])
share|improve this answer
    
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

 
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.