Изменения

Получим элементы объекта по порядку, сначала определим какой элемент будет стоять на 1-м месте,2-м и т.д.Для этого узнаем в какой из "групп", определяемых префиксом 1..Пусть мы нашли первые i, находится наш элементэлементов нашего объекта. <br> Для этого достаточнопросматривать группы в лексикографическом порядке и проверять находимся ли мы в этой "группе", т.е. наш номер принадлежитдиапазону всех вариантов i+1 элемента посчитаем диапазон номеров этой группыобъектвов с данным префиксом. <br> Если принадлежитискомый номер входит в один из диапазонов, то понятноочевидно мы нашли элемент, что который должени стоять на (i+1)-ю позицию следуют поставить соответственный элемент и перейти к построению суффикса, иначе выкинем эту группу полностью из рассмотрения и будем искать номерсреди оставшихсяом месте. <br>

Рассмотрим почему данный алгоритм корректен. Докажем по индукцииНесложно понять, что мы верно выберем первые i-элементов объекта.Условимся, что нумерация обектов начинается с 1. : База: i=0 - очевидно: Докажем, что если первые i-элементов выбраны верно, то i+1 мы также выберем верно : Переход: На i+1-ом шаге мы найдем, какой элемент должен быть i+1-ым для объекта с номером numOfOject, среди всех комбинаторных обектов, которые имеют префикс длины i - как у нас. <br> Рассмотрим искомый объект. Очевидно, что все объекты, у которых символ на i+1 месте меньше чем у нас в лексикографическом порядке, будут идти раньше нас (префикс совпадает, а i+1 символ меньше), т.е. наш номер, по крайней мере больше, количества таких объектов. А те у которых больше будут идти после нас, т.е. даже номер найменьшего из них будет больше нашего. Тогда <br>(суммы всех комбинаторных объектов с ">=" префиксом) >= numOfObject > (суммы всех комбинаторных объектов с меньшим "<" префиксом) <br> т.е. в итоге корректность алгоритма следует из его построения алгоритма мы поставим именно тот элемент, который нам нужен. <br> Далее продолжим искать среди объектов, которые имеют одинаковый префикс длины i+1, изменив номер на номер среди комбинаторных объектов с текущим префиксом. <br>Очевидно, это тоже самое, что искать старый номер, среди старых префиксов.