Изменения

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