множества за <tex>O( log {n}) </tex>. Например декартово дерево по неявному ключу.
== Размещения ==
Рассмотрим алгоритм получения i-го в лексикографическом порядке размещения <tex> A^k_n </tex>
<tex>A^{k}_{n} </tex> ''{{---}} количество размещений из n по k
placement[n] ''{{---}} искомое размещение''
was[n] ''{{---}} использовали ли мы уже эту цифру в размещении''
'''for''' i = 1 '''to''' k '''do''' ''//k - количество цифр в размещении''
alreadyWas = (numOfPlacement-1) div <tex> A^{k-i}_{n-i} </tex> ''// сколько цифр уже полностью заняты размещениями с меньшим номером''
numOfPlacement = ((numOfPlacement-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>.
== Сочетания ==
Рассмотрим алгоритм получения 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>.
== Битовые вектора ==
== Скобочные последовательности ==
== Разложение на слагаемые ==
== См. также ==
[[Получение номера по объекту|Получение номера по объекту]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
