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