Проблема - если все перестановки строки перечислены в алфавитном порядке, мы называем это лексикографическим порядком. Какая n-я лексикографическая перестановка данной строки?
Вместо того, чтобы находить все перестановки и искать n-ю, мы можем напрямую вычислить n-ю перестановку. Чтобы решить этот вопрос, нам нужно сначала понять факторную систему счисления (или факториальную систему счисления). Факториальная система счисления использует факториальные значения вместо степеней чисел (в двоичной системе используются степени 2, десятичные - степени 10) для обозначения разрядов (или основания).
Разрядные значения (базовые):
5!= 120 4!= 24 3!=6 2!= 2 1!=1 0!=1 etc..
Цифра на нулевом разряде всегда равна 0. Цифра на первом месте (с основанием = 1!) Может быть 0 или 1. Цифра на втором месте (с основанием 2!) Может быть 0,1 или 2, и поэтому на. Вообще говоря, цифра на n-м месте может принимать любое значение от 0 до n.
Первые несколько цифр представлены как factoradics-
0 -> 0 = 0*0!
1 -> 10 = 1*1! + 0*0!
2 -> 100 = 1*2! + 0*1! + 0*0!
3 -> 110 = 1*2! + 1*1! + 0*0!
4 -> 200 = 2*2! + 0*1! + 0*0!
5 -> 210 = 2*2! + 1*1! + 0*0!
6 -> 1000 = 1*3! + 0*2! + 0*1! + 0*0!
7 -> 1010 = 1*3! + 0*2! + 1*1! + 0*0!
8 -> 1100 = 1*3! + 1*2! + 0*1! + 0*0!
9 -> 1110
10-> 1200
Существует прямая связь между n-й лексикографической перестановкой строки и ее факторадическим представлением.
Например, вот перестановки строки «abcd».
0 abcd 6 bacd 12 cabd 18 dabc 1 abdc 7 badc 13 cadb 19 dacb 2 acbd 8 bcad 14 cbad 20 dbac 3 acdb 9 bcda 15 cbda 21 dbca 4 adbc 10 bdac 16 cdab 22 dcab 5 adcb 11 bdca 17 cdba 23 dcba
Если внимательно присмотреться, мы можем увидеть здесь закономерность. Первая буква меняется после каждой 6-й (3!) Перестановки. Вторая буква меняется после 2 (2!) Перестановок. Третья буква меняется после каждой (1!) Перестановки, а четвертая буква меняется после каждой (0!) Перестановки. Мы можем использовать это соотношение, чтобы напрямую найти n-ю перестановку.
Как только мы представляем n в фактическом радикальном представлении, мы рассматриваем каждую цифру в нем и добавляем символ из данной строки к выходным данным. Если нам нужно найти 14-ю перестановку «abcd». 14 факторадиков - ›2100г.
Начните с первой цифры - ›2, строка -« abcd ». Предполагая, что индекс начинается с 0, возьмите элемент в позиции 2 из строки и добавьте его в Output.
Output String c abd 2 012
Следующая цифра - ›1.String теперь« abd ». Снова возьмите символ в позиции 1 и добавьте его в Выход.
Output String cb ad 21 01
Следующая цифра - ›0. Строка -« ad ». Добавьте символ в позиции 1 к выходу.
Output String cba d 210 0
Следующая цифра - ›0. Строка -« d ». Добавьте символ в позиции 0 к выходу.
Output String cbad '' 2100
Чтобы преобразовать данное число в факторную систему счисления, последовательно разделите число на 1,2,3,4,5 и так далее, пока частное не станет равным нулю. Напоминания на каждом этапе формируют фактическое представление.
Например, чтобы преобразовать 349 в factoradic,
Quotient Reminder Factorial Representation 349/1 349 0 0 349/2 174 1 10 174/3 58 0 010 58/4 14 2 2010 14/5 2 4 42010 2/6 0 2 242010
Фактическое представительство 349 - это 242010 г.
Код Java -
Код драйвера для тестирования функций в Java -
Note : The length of factoradic representation should be equal to the length of the character array. Prepend zeros to ensure the length is same.
