Determine the $n$th string among those of a given length in alphabetical order starting at a given string and using a given character set?

Question

When building strings using a particular character set (the set can change), such as in a brute-force password cracking, how would I determine which string occurs in the $n$th position when the strings are ordered alphabetically for each length, starting at a given string? (Conversely, what is the position of a given string among those of the same length, starting at a given string of that length?)

For example, if the character set is $ABCDEFG$, then among the strings of length 2, starting at $AA$, string $AC$ is in position 3 and string $AE$ is in position 5:

$$\begin{matrix} \text{position:}&1&2&3&4&5&6&7\\ \text{string:}&AA&AB&AC&AD&AE&AF&AG \end{matrix} $$

I am programming in Delphi and want to use a function that returns the string: function CharArrayPosToStr(ca: TCharArray; len, pos: Integer): String;

The purpose is to break the job into working sets of given lengths, so I need to be able to quickly determine something like: Set 1 starts at $AAAA$ and ends at $AAQA$ and set 2 begins at $AAQB$, etc.

Answer 1

The shortlex ordered list of all words on the seven-letter alphabet $ABCDEFG$ is $$A,B, C, D, E, F, G, AA, AB, ..., GF, GG, AAA, ..., GGG, ...$$

If we replace the letters $A,B,C,D,E,F,G$ with the nonzero digits $1,2,3,4,5,6,7$, then
this becomes the list of positive integers written in bijective base-7 notation (in numerical order): $$1, 2, 3, 4, 5, 6, 7, 11, 12, ..., 76, 77, 111, ..., 777, ...$$

More generally, in the shortlex ordering of all the words on the digit-set $\{1, 2, ..., k\} (k \ge 1)$, the $m$th word is $a_n a_{n−1} ... a_1 a_0$, where

$$\begin{align} a_0 & = m - q_0 k , & & q_0 = f\left(\frac m k \right) \\ a_1 & = q_0 - q_1 k , & & q_1 = f\left(\frac {q_0} k \right) \\ a_2 & = q_1 - q_2 k , & & q_2 = f\left(\frac {q_1} k \right) \\ & \vdots & & \vdots \\ a_n & = q_{n-1} - 0 k , & & q_n = f\left(\frac {q_{n-1}} k \right) = 0 \end{align} $$

and $$f(x) = \lceil x \rceil - 1.$$

So, to find the $m$th word in the shortlex ordering of words on an alphabet of $k$ letters, just use the preceding algorithm to find the bijective base-$k$ numeral for $m$ (and convert back to letters using the reverse substitution).

Also, note that the list-position $m$ of a given word is obtained simply by making the digit-substitution and then reading the result (say $a_n a_{n−1} ... a_1 a_0$) as a bijective base-$k$ numeral: $$ m = (a_n a_{n−1} ... a_1 a_0)_{\text{bijective base-}k} = a_n\ k^n + a_{n-1}\ k^{n-1} + ... + a_1\ k^1 + a_0\ k^0.$$

NB:
If you're interested in the positions of certain words relative to that of others (i.e. in a particular list segment), just find the relative position by the appropriate subtractions.

Answer 2

I realize this is an old thread, but the problem seemed familiar, and I recognized I've had a solution for years. In VBA, you can do it like this:

Function ShortlexPos(sInp As String, sSym As String) As Long
  If Len(sInp) Then ShortlexPos = InStr(sSym, Right(sInp, 1)) _
     + Len(sSym) * ShortlexPos(Left(sInp, Len(sInp) - 1), sSym)
End Function

For example, columns in Excel are named

A, B, ..., Y, Z, AA, AB, ..., AX, AY, AZ, BA, ... XFD

The position of the last column is given by

ShortlexPos("XFD", "ABCDEFGHIJKLMNOPQRSTUVWXYZ")

... which (correctly) returns 16384.

The complementary function returns the sequence at a given position:

Function ShortLexStr(iNum As Long, sSym As String) As String
  If iNum > 0 Then ShortlexStr = ShortlexStr((iNum - 1) \ Len(sSym), sSym) & _
   Mid(sSym, ((iNum - 1) Mod Len(sSym)) + 1, 1)
End Function

For example,

ShortLexStr(16384, "ABCDEFGHIJKLMNOPQRSTUVWXYZ")

returns XFD