# Given a list of strings enumerated over a finite alphabet, what's the most efficient way to get a string by its index?

Say you have the finite alphabet $$\{a,b,c,d,e,f,g\}$$ and an enumeration of finite strings over it by the shortlex order (length-lexicographic ordering), starting with the empty string, i.e., $$\epsilon, a, b, c, d, e, f, g,$$ $$aa, ab, ac, \cdots,$$ $$gg, \cdots, aaa, aab, aac,$$ $$\cdots, ggg, \cdots$$.

What's the most efficient algorithm to get a string from that sequence by its index? For example, given 9, we should get $$ab$$.

Basically, I'm looking for a fast procedure that takes an integer $$x$$ and returns the $$x$$-th string from a list of strings enumerated over a fixed, finite alphabet.

• Do you have some kind of ordering of the strings in the list? Commented Jun 1, 2022 at 0:01
• @Russel Yes, the same ordering as the set of natural numbers. Commented Jun 1, 2022 at 1:04
• What do you mean by the set of natural numbers? Do you mean lexicographically by length? Say like this $[\epsilon, a, b, c, d, e, f ,g, aa, ab, ac, ...]$ using the alphabet you gave and $\epsilon$ is the empty string? In that case, I think DW's answer suffice for this. Commented Jun 1, 2022 at 1:14
• Isn't this the same as base conversion? For example: The math behind converting from any base to any base without going through base 10? Commented Jun 1, 2022 at 15:16

Easier problem: Suppose you want the $$i$$th string, from all length-$$k$$ strings over that template. Can you find the $$i$$th string? This is easy. I'll let you figure out how to do that.
Your problem: Suppose you want the $$i$$th string. Well, there are $$1+6+6^2+\dots+6^k$$ strings of length $$\le k$$ over this alphabet. So, find the smallest $$k$$ such that $$i \le 1+6+6^2+\dots+6^k$$; then you know that the output needs to be a length-$$k$$ string. Let $$j=i-(1+6+6^2+\dots+6^{k-1})$$; and find the $$j$$th string, from all length-$$k$$ strings.