1632
правки
Изменения
м
rollbackEdits.php mass rollback
numOfObject -= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i)
'''else'''
object[i] = j break
'''return''' object
Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью.
'''else'''
bitvector[i] = 0
'''return''' bitvecor bitvector
Данный алгоритм работает за <tex>O(n)</tex>, так как в случае битовых векторов <tex>k</tex> не зависит от <tex>n</tex>.
Алгоритм эквивалентен переводу числа из десятичной системы в двоичную.
*<tex>\mathtt{n!}</tex> {{---}} количество перестановок размера <tex>n</tex>,
*<tex>\mathtt{permutation[n]}</tex> {{---}} искомая перестановка,
*<tex>\mathtt{was[n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,.
На <tex>i</tex>-ом шаге:
*<tex>\mathtt{alreadyWas}</tex> {{---}} сколько цифр уже полностью заняты перестановками с меньшим номером,
*мы должны поставить ту цифру, которая еще полностью не занята, то есть цифру с номером <tex>alreadyWas + 1</tex>. Среди цифр, которых еще нет в нашем префиксе, считаем, что это цифра <tex>j</tex>,.
На <tex>j</tex>-ом шаге:
*<tex>\mathtt{curFree}</tex> {{---}} если элемент с номером <tex>j</tex> свободен, то он имеет номер curFree среди всех свободных элементов с <tex>1</tex> по <tex>j</tex>,.
'''list<int>''' num2permutation(k: '''int'''):
'''for''' i = 1 '''to''' n
== Сочетания ==
На каждой итерации мы проверяем, входит ли число <tex>\mathtt{next}</tex> в искомое сочетание. Если мы хотим взять <tex>\mathtt{next}</tex>, то номер перестановки сочетания должен быть меньше, чем <tex dpi=140>\binom{n - 1}{k - 1}</tex>, так как потом надо будет выбрать <tex>k - 1</tex> элемент из <tex>n - 1</tex> доступных. Если нет, то будем считать, что <tex dpi=140>\binom{n - 1}{k - 1}</tex> перестановоксочетаний, начинающихся с <tex>\mathtt{next}</tex>, мы пропустили. В обоих случаях рассмотрение текущего числа <tex>next</tex> мы заканчиваем и переходим к следующему числу.
*<tex>\mathtt{choose}</tex> {{---}} искомое сочетание,
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,
'''if''' m < C[n - 1][k - 1]
choose.push_back(next)
k = k -1
'''else'''
m -= C[n - 1][k - 1]
'''return''' choose
Асимптотика приведенного алгоритма {{---}} <tex>O(n)</tex>, предподсчет <tex>\mathtt{C[n][k]}</tex> {{---}} <tex>O(n^2)</tex>
== См. также ==
*[[Получение номера по объекту|Получение номера по объекту]]
