88
правок
Изменения
Нет описания правки
Рассмотрим алгоритм получения i-ой в лексикографическом порядке перестановки.
'''<tex>f[n]=n!</tex>'''
'''<tex>ans[n]</tex> ''//искомая перестановка'''
'''<tex>was[n]</tex> ''//использовали ли мы уже эту цифру в переставновке'''
'''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> n </tex> '''do ''// n-это количество цифр в перестановке'''''
'''AlreadyWas <tex> i \leftarrow </tex> (NumOfPermutation-1) div f[n-i] ''// сколько цифр уже полностью заняты предыдущими перестановками'''''
'''''//тогда очевидно сейчас мы должны поставить ту цифру которая еще полностью не занята, т.е. AlreadyWas+1 - ую''''' '''for''' <tex> j \leftarrow 1 </tex> '''to''' <tex> n </tex> '''do''' '''if''' <tex> was[j] = FALSE </tex> '''then ''' <tex> CntFree++ </tex> '''if''' <tex> CntFree = AlreadyWas+1 </tex> '''then ''' <tex> ans[i] \leftarrow j </tex> <tex> was[j] \leftarrow TRUE </tex>
== Сочетания ==
