Изменения

: Несложно понять, что корректность алгоритма следует из его построения.: Сложность алгоритма <tex>O(n^{2}f(1..i)) </tex>, где <tex>f(1..i)</tex> - сложность вычисления количества комбинаторных объектов с данным префиксом.

was[n] ''{{- --}} использовали ли мы уже эту цифру в перестановке''

== Сочетания Размещения ==

== Размещения Сочетания ==Рассмотрим алгоритм получения i-го в лексикографическом порядке сочетания <tex> С^k_n </tex> <tex>С^{k}_{n} </tex> ''{{---}} количество сочетаний из n по k combination[n] ''{{---}} искомое сочетание'' was[n] ''{{---}} использовали ли мы уже эту цифру в сочетании'' '''for''' i = 1 '''to''' k '''do''' ''//k - количество цифр в сочетании'' ''// вычтем те "группы" где, i-цифра меньше искомой'' numOfCombination = ((numOfCombination-1) mod <tex> A^{k-i}_{n-i} </tex>) + 1 ''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1, которая еще не занята'' '''for''' j = 1 '''to''' n '''do''' '''if''' was[j] = false '''then ''' cntFree++ '''if''' cntFree = alreadyWas+1 '''then ''' ans[i] = j was[j] = trueСложность алгоритма <tex>O(nk) </tex>.