0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Do you have some kind of ordering of the strings in the list? $\endgroup$
    – Russel
    Commented Jun 1, 2022 at 0:01
  • $\begingroup$ @Russel Yes, the same ordering as the set of natural numbers. $\endgroup$
    – Quavo
    Commented Jun 1, 2022 at 1:04
  • $\begingroup$ 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. $\endgroup$
    – Russel
    Commented Jun 1, 2022 at 1:14
  • $\begingroup$ 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? $\endgroup$ Commented Jun 1, 2022 at 15:16

1 Answer 1

2
$\begingroup$

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.

I'm guessing you can take it from here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.