88
правок
Изменения
Нет описания правки
== Перестановки ==
Рассмотрим алгоритм получения i-ой в лексикографическом порядке перестановкиразмера n.
f[n]=n!
permutation[n] ''//искомая перестановка''
== Сочетания ==
Рассмотрим алгоритм получения 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
== Размещения ==
== Битовые вектора ==
== Скобочные последовательности ==
== Разложение на слагаемые ==
