1632
правки
Изменения
м
rollbackEdits.php mass rollback
== Описание алгоритма ==
Получаем элементы объекта по порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы нашли первые <tex>i</tex> элементов объекта. Для всех вариантов элемента, который может стоять на позиции с номером <tex>i+1</tex>, посчитаем диапазон номеров, который будет соответствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должен стоять на месте с номером <tex>i+1</tex>. Диапазоны номеров не пересекаются, значит на это место больше нельзя поставить никакой другой элемент.:
*В в начале каждого шага <tex>\mathtt{numOfObject}</tex> {{---}} номер нужного объекта среди тех, у которых префикс до <tex>i</tex>-го элемента лексикографически равен префиксу нашего объекта,
*<tex>\mathtt{n}</tex> {{---}} количество мест в комбинаторном объекте (например, битовый вектор длины <tex>n</tex>),
*<tex>\mathtt{k}</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2</tex>, поскольку возможны только <tex>0</tex> и <tex>1</tex>. Все элементы занумерованы в лексикографическом порядке, начиная с <tex>1</tex>,.
Комбинаторные объекты занумерованы с <tex>0</tex>. Переход к нумерации с единицы можно сделать с помощью одной операции декремента перед проходом алгоритма:
'''function''' num2object(numOfObject: '''int'''):
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>
== См. также ==
*[[Получение номера по объекту|Получение номера по объекту]]
