1632
правки
Изменения
м
'''for''' На каждой итерации мы проверяем, входит ли число <tex>\mathtt{next}</tex> в искомое сочетание. Если мы хотим взять <tex>\mathtt{next}</tex>, то номер сочетания должен быть меньше, чем <texdpi=140>v \in Vbinom{n - 1}{k - 1}</tex> '''do''' , так как потом надо будет выбрать <tex>k - 1</tex> элемент из <tex>n - 1</tex> доступных. Если нет, то будем считать, что <texdpi=140>d[v] \gets +binom{n - 1}{k - 1}</tex> сочетаний, начинающихся с <tex>\inftymathtt{next}</tex>, мы пропустили. В обоих случаях рассмотрение текущего числа <tex>next</tex>мы заканчиваем и переходим к следующему числу. *<tex>d[s] \gets 0mathtt{choose}</tex>{{---}} искомое сочетание, '''for''' *<tex>i \gets 1mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex> '''to''' , <tex>|V| - \mathtt{C[n][0] = 1}</tex>, '''do forlist<int>''' <math>num2choose(un, vk, m: '''int''') \in E</math: next = 1 '''while''' k >0 '''if''' m <tex>dC[vn - 1] > d[uk - 1] + w choose.push_back(u, vnext)</tex> k = k - 1 '''thenelse''' <tex>d m -= C[vn - 1] \gets d[uk - 1] n = n - 1 next = next + w(u, v)</tex>1 '''return''' chooseАсимптотика приведенного алгоритма {{---}} <tex>O(n)</tex>, предподсчет <tex>\mathtt{C[n][k]}</tex> {{---}} <tex>dO(n^2)</tex> == Размещения См. также ==*[[Получение номера по объекту|Получение номера по объекту]]*[[Получение_предыдущего_объекта#.D0.A1.D0.BF.D0.B5.D1.86.D0.B8.D0.B0.D0.BB.D0.B8.D0.B7.D0.B0.D1.86.D0.B8.D1.8F_.D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D0.B0_.D0.B4.D0.BB.D1.8F_.D0.B3.D0.B5.D0.BD.D0.B5.D1.80.D0.B0.D1.86.D0.B8.D0.B8_.D0.BF.D1.80.D0.B5.D0.B4.D1.8B.D0.B4.D1.83.D1.89.D0.B5.D0.B3.D0.BE_.D1.81.D0.BE.D1.87.D0.B5.D1.82.D0.B0.D0.BD.D0.B8.D1.8F|Получение предыдущего сочетания]]*[[Получение_следующего_объекта#.D0.A1.D0.BF.D0.B5.D1.86.D0.B8.D0.B0.D0.BB.D0.B8.D0.B7.D0.B0.D1.86.D0.B8.D1.8F_.D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D0.B0_.D0.B4.D0.BB.D1.8F_.D0.B3.D0.B5.D0.BD.D0.B5.D1.80.D0.B0.D1.86.D0.B8.D0.B8_.D1.81.D0.BB.D0.B5.D0.B4.D1.83.D1.8E.D1.89.D0.B5.D0.B3.D0.BE_.D1.81.D0.BE.D1.87.D0.B5.D1.82.D0.B0.D0.BD.D0.B8.D1.8F|Генерация следующего сочетания]]== Битовые вектора Источники информации ==== Скобочные последовательности ==*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31 - ISBN 5-94774-010-9[[Категория: Дискретная математика и алгоритмы]][[Категория: Комбинаторика]]
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'''):
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' k
'''if''' j-й элемент можно поставить на i-e место
'''if''' numOfObject >= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i)
numOfObject -= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i)
'''else'''
object[i] = j
break
'''return''' object
Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью.
Приведем примеры получения некоторых [[Комбинаторные объекты|комбинаторных объектов]] по номеру.
== Битовые вектора ==
Рассмотрим алгоритм получения <tex>k</tex>-ого в лексикографическом порядке битового вектора размера <tex>n</tex>.
При построении битовых векторов можно не проверять условие возможности постановки какого-то объекта на текущее место. На каждый позиции может стоять один из двух элементов, независимо от того, какие элементы находятся в префиксе. Так как у нас всего два возможных элемента, упростим второй цикл до условия:
*<tex>\mathtt{bitvector[n]}</tex> {{---}} искомый битовый вектор,
*<tex>\mathtt{numOfBitvector}</tex> {{---}} номер искомого вектора среди всех битовых векторов,
*<tex>\mathtt{pow(2, n)}</tex> {{---}} <tex>2^{n}</tex> количество битовых векторов длины <tex>n</tex>,
'''vector<int>''' num2bitvector(numOfBitvector: '''int'''):
'''for''' i = 1 '''to''' n
'''if''' numOfBitvector >= pow(2, (n - i))
numOfBitvector -= pow(2, (n - i))
bitvector[i] = 1
'''else'''
bitvector[i] = 0
'''return''' bitvector
Данный алгоритм работает за <tex>O(n)</tex>, так как в случае битовых векторов <tex>k</tex> не зависит от <tex>n</tex>.
Алгоритм эквивалентен переводу числа из десятичной системы в двоичную.
== Перестановки ==
Рассмотрим алгоритм получения i<tex>k</tex>-ой в [[Лексикографический порядок|лексикографическом порядке ]] перестановки. '''размера <f[tex>n]=n! '''ans[n] ''<//искомая перестановка'''''tex>. '''was[n] ''//использовали ли мы уже эту цифру в переставновке''''' '''for''' i = 1 '''to''' n '''do ''//n-это Заметим, что всем префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество цифр в перестановке''''' ''' alreadyWas = (numOfPermutation-1всевозможных суффиксов зависит только от длины) div f[n-i] ''' ''' numOfPermutation = то есть можем просто посчитать "количество диапазонов, которые идут до нас" (numOfPermutation-1) mod f[n-i] ''// сколько количество цифр уже полностью заняты предыдущими занятых перестановками''''' '''''/с меньшим номером) за <tex>O(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] =w true tex>:
*<tex>\mathtt{k}</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
alreadyWas = k / (n - i)!
k %= (n - i)!
curFree = 0
'''for''' j = 1 '''to''' n
'''if''' was[j] == ''false''
curFree++
'''if''' curFree == alreadyWas + 1
permutation[i] = j
was[j] = true
'''return''' permutation
Данный алгоритм работает за <tex>O(n^2)</tex>, так как в случае перестановок <tex>n=k</tex>. Мы можем посчитать все <tex>\mathtt{n!}</tex> за <tex>O(n) </tex>. Асимптотику можно улучшить
до <tex>O(n \log {n}) </tex>, если использовать структуры данных (например, [[Декартово дерево|декартово дерево]] по неявному ключу), которые позволяют искать <tex>i</tex>-й элемент множества и удалять элемент
множества за <tex>O( \log {n}) </tex>.
== Сочетания ==
