n-th item of the series of strings from set of characters

Question

Consider a set of Characters like S={ABCDEFGHIJKLMNOPQRSTUVWXYZ} where S is 26.

R=3, where R is length of every item of the series.

Total Output is $S^R$ = $26^3$ = 17576 where first item is AAA and the last item is ZZZ

All the possible output or series is

AAA, AAB, AAC, AAD, AAE…....AAZ, ABA, ABB, ABC, ABD…...…ZZW, ZZX, ZZY, ZZZ.

I need an algorithm or a formula to find a n-th item of the series. Like 500th item is ATF, 1000th item is BML and 17576th item is ZZZ.

Please see the full series here.

Please suggest me with an algorithm or a formula to achieve this target.

Answer 1

You know that there are $26^3 = 17,576$ three-letter sequences that can be formed from the English alphabet. By symmetry, each first letter corresponds to $26^2 = 676$ of these sequences and each set of first two letters corresponds to $26$ of these sequences.

How to show that ATF is in the $500$th position:

Since $500 < 26^2 = 676$ and there are $676$ subsequences that begin with each letter, the $500$th position is in the first cycle of two-letter sequences of the alphabet. Therefore, the sequence must begin with A. If we divide $500$ by $26$, we obtain a quotient of $19$ and a remainder of $6$. Hence, the sequence in the $500$th position is in the twentieth full cycle of the alphabet since $19 \cdot 26 = 494 < 500 < 20 \cdot 26 = 520$. The twentieth letter of the alphabet is T, so there must be a T in the second position. The remainder $6$ tells us that the third letter in the sequence is the sixth letter of the alphabet, namely F.

How to show that BML is in the $1000$th position:

Since $26^2 = 676 < 1000 < 1352 = 2 \cdot 676$, the $1000$th position is in the second full cycle of two-letter sequences of the alphabet. Since B is the second letter of the alphabet, the first letter of the sequence is B. Since $1000 = 676 + 324$ and $324 = 12 \cdot 26 + 12$, the sequence in the $1000$th position must be in the $13$th cycle of two-letter sequences of the alphabet since $12 \cdot 26 = 312 < 324 < 338 = 13 \cdot 26$. Since the thirteenth letter of the alphabet is M, there must be an M in the second position of the sequence. Finally, the remainder $12$ tells us that the last letter of the sequence must be the twelfth letter of the alphabet, namely L.

We have to be careful when a sequence ends with the letter Z.

Recall that $1352 = 2 \cdot 676$.

What sequence is in the $1352$nd position?:

We know that $1352 = 2 \cdot 676$. That means the sequence in the $1352$nd position completes two full cycles of two-letter sequences. The second cycle has a B in the first position and ends with ZZ, so the sequence is BZZ.

Observe that $125 \cdot 26 = 3250$.

What sequence is in the $3250$th position?

Since $125 = 4 \cdot 676 + 546$, four letters of the alphabet precede the letter in the first position of the sequence. Since the fifth letter of the alphabet is E, the sequence begins with the letter. Since $546 = 21 \cdot 26$, the two-letter subsequence that follows E completes $21$ full cycles of the alphabet. Since the $21$st letter of the alphabet is U, the letter in the second position of the sequence is U. Since the alphabet ends with Z, the letter in the last position is Z. Hence, the sequence in the $3250$th position is EUZ.

Some observations:

1. Notice that \begin{align*} 500 & \approx 676 \cdot 0.739644970414\\ 1000 & \approx 676 \cdot 1.47928994083\\ 1352 & = 676 \cdot 2\\ 3250 & = 676 \cdot 4.80769230769\\ \end{align*} The sequence in the $500$th position begins with A, the first letter in the alphabet. The sequences in the $1000$th and $1352$nd position each begin with B. The sequence in the $3250$th position begins with E. Observe that \begin{align*} \left\lceil \frac{500}{676} \right\rceil & = \lceil 0.739644970414 \rceil = 1\\ \left\lceil \frac{1000}{676} \right\rceil & = \lceil 1.47928994083 \rceil = 2\\ \left\lceil \frac{1352}{676} \right\rceil & = \lceil 2 \rceil = 2\\ \left\lceil \frac{3250}{676} \right\rceil & = \lceil 4.80769230769 \rceil = 5 \end{align*} the ceiling function $\lceil x \rceil$ yields the least integer greater than or equal to the real number $x$. That is, the position in the alphabet of the first letter of the sequence in position $n$ is given by $$\left\lceil \frac{n}{676} \right\rceil$$
2. If the remainder of the first division is zero, then the sequence ends with ZZ. If the remainder of the first division is not $0$, we divide it by $26$. Observe that \begin{align*} \frac{500}{26} & \approx 19.2307692308\\ \frac{324}{26} & \approx 12.4615384615\\ \frac{546}{26} & = 21 \end{align*} and that \begin{align*} \left\lceil \frac{500}{26} \right\rceil & = 20\\ \left\lceil \frac{324}{26} \right\rceil & = 13\\ \left\lceil \frac{546}{26} \right\rceil & = 21 \end{align*} We found that the sequence in the $500$th position has a T in the second position, the sequence in the $1000$th position has a M in the second position, and the sequence in the $3250$th position has a U in the second position. Thus, if the sequence does not end in ZZ, then the position in the alphabet of the second letter of the sequence is found by applying the ceiling function to the quotient of the remainder of the first division and $26$.

Algorithm: Given $n$ satisfying $1 \leq n \leq 17,576$,

1. Divide $n$ by $26^2 = 676$. Then the position of the first letter of the sequence in the alphabet is $$\left\lceil \frac{n}{26^2} \right\rceil$$

2. If the remainder of the first calculation is $0$, then the last two letters of the sequence are ZZ. Otherwise, divide the remainder $r$ of the first calculation by $26$. Then $$\left\lceil \frac{r}{26} \right\rceil$$ is the position of the second letter in the sequence in the alphabet.

3. If the remainder of the second division is $0$, then the last letter of the sequence is Z. Otherwise, the remainder of the second division tell us the position of the third letter of the sequence in the alphabet.

There are $26^R$ sequences with $R$ letters. The $n$th sequence with $R$ letters has first letter whose position in the alphabet is given by $$\left\lceil \frac{n}{26^{R - 1}} \right\rceil$$ If the remainder of the first division is $0$, the last $R - 1$ letters of the sequence are all Zs. Otherwise, the sequence has second letter whose position in the alphabet is given by $$\left\lceil \frac{r_1}{26^{R - 2}} \right\rceil$$ where $r_1$ is the remainder of the first division. If the remainder of the second division is $0$, the last $R - 2$ positions of the sequence are all Zs. Otherwise, the sequence has third letter whose position in the alphabet is given by $$\left\lceil \frac{r_2}{26^{R - 3}} \right\rceil$$ where $r_2$ is the remainder of the second division. Continuing in this way, we see that if the remainder of the $k$th division is $0$, the remaining $R - k$ positions of the sequence are all Zs. Otherwise, the position in the alphabet of the $k$th letter of the sequence is $$\left\lceil \frac{r_{k - 1}}{26^{R - k}} \right\rceil$$ where $r_{k - 1}$ is the remainder of the $(k - 1)$st division.