88
правок
Изменения
Нет описания правки
== Перестановки ==
Рассмотрим алгоритм получения i-ой в лексикографическом порядке перестановки.
'''<tex>f[n]=n!</tex> '''<tex>ans[n]</tex> ''//искомая перестановка''''' '''<tex>was[n]</tex> ''//использовали ли мы уже эту цифру в переставновке''''' '''for''' <tex> i = 1 </tex> '''to''' <tex> n </tex> '''do ''//n-это количество цифр в перестановке''''' '''<tex> alreadyWas = (numOfPermutation-1) div f[n-i] </tex> ''' '''<tex> numOfPermutation = (numOfPermutation-1) mod f[n-i] </tex> ''// сколько цифр уже полностью заняты предыдущими перестановками'''''
'''''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. AlreadyWas+1'''''
'''for''' <tex> j = 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] = j </tex> <tex> was[j] =w true </tex>
