Изменения
Нет описания правки
''k {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте (элемент лексикографически меньше другого, если номер элемента меньше номера другого) (например для битового вектора k=2 : возможны только 0 и 1)''
Несложно понять, что корректность алгоритма следует из его построения.
Сложность алгоритма <tex>O(nkf(1..i)) </tex>, где <tex>f(1..i)</tex> - сложность вычисления количества комбинаторных объектов с данным префиксом. Основную сложность при построении алгоритмов генерации комбинаторных объектов составляет вычисление количества комбинаторных объектов с данным префиксом. Приведем примеры способов получения некоторых из [[Комбинаторные объекты|комбинаторных объектов]] по номеру.
''мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1 - ую, которой еще нет в нашем префиксе, пусть это цифра j''
Данный алгоритм работает за <tex>O(n^2) </tex> (n=k). Мы можем посчитать все <tex>P_{n} </tex> за <tex>O(n) </tex>. Асимптотику можно улучшить
