Эффективно вычислять индекс определенного элемента в лексикографическом порядке

У меня есть четыре элемента:

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, но мне кажется, что должно быть общее решение, которого я не вижу?


c++ element indexing lexicographic
person kunterbunt    schedule 18.08.2014    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Разве это не просто

(4 ^ (n - 1)) * val(string[0])
+ (4 ^ (n - 2)) * val(string[1])
+ ...
+ (4 ^ (0)) * val(string[n-1])

Вы, вероятно, запрограммировали бы это с помощью цикла.

person BrettFromLA    schedule 18.08.2014
comment
Ах, спасибо, так это действительно было так просто. Должно быть, я слишком устал, чтобы найти это самому. - person kunterbunt; 19.08.2014

arrow_upward
1
arrow_downward

Если вы замените эти буквы {A, B, C, D} на числа {0, 1, 2, 3}, вы обнаружите, что это просто четверичная запись, или предположим, что у вас есть 10 букв {A, B, C, D , E, F, G, H, I, J} и измените их на 0 -- 9, это будет похоже на знакомую нам десятичную запись. Итак, в четвертичной системе АА = 00, ДД = 33, переход в десятичную будет 3*4+3=15, индекс ВС будет 1*4+2 = 6.

person dguan    schedule 18.08.2014