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