Изменения
Нет описания правки
'''for''' i = 1 '''to''' n '''do'''
'''for''' j = 1 '''to''' k '''do'''
'''if''' элемент j можно поставить на i-e место'''{''' '''then if''' numOfObject > (количество комбинаторных обектов с данным префиксом)''' '{''then''' numOfObject -= (количество комбинаторных обектов с данным префиксом) '''} else{''' '''then''' ans[i]=j break '''}''' '''}'''
Несложно понять, что корректность алгоритма следует из его построения.
Сложность алгоритма <tex>O(nkf(1..i)) </tex>, где <tex>f(1..i)</tex> - сложность вычисления количества комбинаторных объектов с данным префиксом. Основную сложность при построении алгоритмов генерации комбинаторных объектов составляет вычисление количества комбинаторных объектов с данным префиксом. Приведем примеры способов получения некоторых из [[Комбинаторные объекты|комбинаторных объектов]] по номеру.
*мы должны поставить ту цифру, которая еще полностью не занята, то есть <tex>alreadyWas+1</tex> - ую, которой еще нет в нашем префиксе, считаем, что это цифра <tex>j</tex>
'''for''' i = 1 '''to''' n '''do''' '''{'''
alreadyWas = (numOfPermutation-1) div <tex>P_{n-i} </tex>
numOfPermutation = ((numOfPermutation-1) mod <tex>P_{n-i} </tex>) + 1
ans[i] = j (посчитаем за <tex>O(n) </tex>)
теперь j-ый элемент занят (находится в нашем префиксе)
'''}'''
Данный алгоритм работает за <tex>O(n^2) </tex> (n=k). Мы можем посчитать все <tex>P_{n} </tex> за <tex>O(n) </tex>. Асимптотику можно улучшить
до <tex>O(n \log {n}) </tex>, если использовать структуры данных, которые позволяют искать i-ый элемент множества и удалять элемент
