Эффективно рассчитать индекс конкретного элемента в лексикографическом порядке
У меня есть четыре элемента:
A B C D
Я могу организовать все перестановки n elements в лексикографическом порядке, так что для n=2:
0=AA 1=AB 2=AC 3=AD ... 15=DD
Как можно, не прибегая к подсчету, рассчитать индекс в этом порядке для определенного элемента?
Когда я перечисляю свои элементы 0=A 1=B 2=C 3=D и есть строка string Я могу рассчитать индекс, как это для n=2
4 * val(string[0]) + val(string[1])
string="AC" -> 4*0 + 2 = 2
string="DD" -> 4*3 + 3 = 15
Как я могу найти индекс для любой строки и n > 2? Мне это действительно нужно только для n=2,3,4,5, но такое ощущение, что должно быть общее решение, которого я не вижу?
Решение
Разве это не просто
(4 ^ (n - 1)) * val(string[0])
+ (4 ^ (n - 2)) * val(string[1])
+ ...
+ (4 ^ (0)) * val(string[n-1])
Вы, вероятно, запрограммируете это с помощью цикла.
Другие решения
Если вы измените эти буквы {A, B, C, D} на числа {0, 1, 2, 3}, вы обнаружите, что это просто четвертичная запись, или предположим, что у вас есть 10 букв {A, B, C, D , E, F, G, H, I, J} и измените их на 0 — 9, это будет похоже на нашу знакомую десятичную запись. Таким образом, в четвертичной системе AA = 00, DD = 33 с переходом в десятичное число будет 3 * 4 + 3 = 15, индекс BC будет 1 * 4 + 2 = 6.