Math - Найдите количество перестановок между двумя строками

Question

Это не домашнее задание =). Я делаю проект, который автоматически генерирует список последовательных имен компьютеров, и я хочу добавить предупреждение, если список будет сумасшедшим длинным списком.

Я знаю, как найти количество перестановок от A-ZZZ, но у меня есть время, пытаясь применить набор исключения включения. Вот сценарий, чтобы сохранить его простым, набор символов будет только A - Z, и регистр нечувствителен к регистру, поэтому «A» = «a».

Пользователь вводит диапазон «ABC» в «AX». Так что единственное, что мне нужно, это между этими двумя. Таким образом, логика psudo получит полный общий счет A - ZZZ, тогда мне нужно исключить, все до «ABC» и все после «AX».

Итак, вопрос в том, как найти счет перед «ABC» и после «AX». Я смотрел на все свои старые дискретные и стат-математические книги, но ничего не подходит, или дает правильный ответ при подключении чисел (n!/N1! * N2! ...). Я даже пытался сделать что-то вроде преобразования двоичного или шестнадцатеричного в десятичное, но, как вы знаете, это эпическая ошибка =).

Спасибо,

Dave

Answer 1

Самое простое решение рассмотреть обе строки в качестве чисел в базовом 26 представления:

ABC = 26^2 * 0 + 26^1 * 1 + 26^0 * 2 = 28(base 10) 
ACC = 26^2 * 0 + 26^1 * 2 + 26^0 * 2 = 54(base 10) 

ACC - ABC = 54 - 28 = 26 

Так есть в общей сложности 27 строк в диапазоне [ABC, ACC].

Основная идея заключается в использовании positional numeral system с базой 26 (все буквы от А - Z).

Есть только одна проблема с этим подходом:
Он не способен обрабатывать пустые символы, поскольку те, которые не соответствуют «по-умолчанию» -поведению, в том смысле, что они могут отображаться только как префикс.

Обходной к этой проблеме была бы расширить наше ценностное отображение из

A = 0, B = 1, ..., Z = 25 

в

empty = -1, A = 0, ..., Z = 25 

В то время как это нарушает определение системы счисления, мы теперь способны обрабатывать более короткие строки:

magnitude([ZZ, AAA]) = AAA - ZZ + 1 = 0 - (-1) + 1 = 2