http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=Dima32mlВикиконспекты - Вклад участника [ru]2026-08-03T23:04:04ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D0%B0_%D0%BF%D0%BE_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D1%83&diff=42174Получение объекта по номеру2014-12-14T11:31:38Z<p>Dima32ml: /* Перестановки */</p>
<hr />
<div>== Описание алгоритма ==<br />
Получаем элементы объекта по порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы нашли первые <tex>i</tex> элементов объекта. Для всех вариантов элемента, который может стоять на позиции с номером <tex>i+1</tex>, посчитаем диапазон номеров, который будет соответствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должен стоять на месте с номером <tex>i+1</tex>. Диапазоны номеров не пересекаются, значит на это место больше нельзя поставить никакой другой элемент.<br />
<br />
*В начале каждого шага <tex>\mathtt{numOfObject}</tex> {{---}} номер нужного объекта среди тех, у которых префикс до <tex>i</tex>-го элемента лексикографически равен префиксу нашего объекта. <br />
<br />
*<tex>\mathtt{n}</tex> {{---}} количество мест в комбинаторном объекте (например, битовый вектор длины <tex>n</tex>)<br />
<br />
*<tex>\mathtt{k}</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2</tex>, поскольку возможны только <tex>0</tex> и <tex>1</tex>. Все элементы занумерованы в лексикографическом порядке, начиная с <tex>1</tex>.<br />
Комбинаторные объекты занумерованы с <tex>0</tex>. Переход к нумерации с единицы можно сделать с помощью одной операции декремента перед проходом алгоритма. <br />
'''function''' num2object(numOfObject: '''int''')<br />
'''for''' i = 1 '''to''' n <br />
'''for''' j = 1 '''to''' k <br />
'''if''' j-й элемент можно поставить на i-e место <br />
'''if''' numOfObject >= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i)<br />
numOfObject -= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i)<br />
'''else'''<br />
object[i] = j <br />
'''return''' object<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью. <br />
Приведем примеры получения некоторых [[Комбинаторные объекты|комбинаторных объектов]] по номеру.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения <tex>k</tex>-ой в [[Лексикографический порядок|лексикографическом порядке]] перестановки размера <tex>n</tex>.<br />
Заметим, что всем префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество всевозможных суффиксов зависит только от длины) то есть можем просто посчитать "количество диапазонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>:<br />
<br />
*<tex>\mathtt{k}</tex> {{---}} номер искомой последовательности<br />
<br />
*<tex>\mathtt{n!}</tex> {{---}} количество перестановок размера <tex>n</tex>.<br />
<br />
*<tex>\mathtt{permutation[n]}</tex> {{---}} искомая перестановка.<br />
<br />
*<tex>\mathtt{was[n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
На <tex>i</tex>-ом шаге:<br />
<br />
*<tex>\mathtt{alreadyWas}</tex> {{---}} сколько цифр уже полностью заняты перестановками с меньшим номером.<br />
<br />
*мы должны поставить ту цифру, которая еще полностью не занята, то есть цифру с номером <tex>alreadyWas + 1</tex>. Среди цифр, которых еще нет в нашем префиксе, считаем, что это цифра <tex>j</tex>.<br />
<br />
На <tex>j</tex>-ом шаге:<br />
<br />
*<tex>\mathtt{curFree}</tex> {{---}} если элемент с номером <tex>j</tex> свободен, то он имеет номер curFree среди всех свободных элементов с <tex>1</tex> по <tex>j</tex><br />
'''function''' num2permutation(k: '''int''')<br />
'''for''' i = 1 '''to''' n '''do''' <br />
alreadyWas = k div (n-i)! <br />
k = k mod (n-i)!<br />
curFree = 0<br />
'''for''' j = 1 '''to''' n <br />
'''if''' was[j] == false <br />
curFree++<br />
'''if''' curFree == alreadyWas + 1<br />
permutation[i] = j<br />
was[j] = true<br />
'''return''' permutation<br />
<br />
Данный алгоритм работает за <tex>O(n^2)</tex>, так как в случае перестановок <tex>n=k</tex>. Мы можем посчитать все <tex>\mathtt{n!}</tex> за <tex>O(n) </tex>. Асимптотику можно улучшить <br />
до <tex>O(n \log {n}) </tex>, если использовать структуры данных (например, [[Декартово дерево|декартово дерево]] по неявному ключу), которые позволяют искать <tex>i</tex>-й элемент множества и удалять элемент <br />
множества за <tex>O( \log {n}) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения <tex>k</tex>-ого в лексикографическом порядке битового вектора размера <tex>n</tex>.<br />
При построении битовых векторов можно не проверять условие возможности постановки какого-то объекта на текущее место. На каждый позиции может стоять один из двух элементов, независимо от того, какие элементы находятся в префиксе. Так как у нас всего два возможных элемента, упростим второй цикл до условия: <br />
<br />
*<tex>\mathtt{bitvector[n]}</tex> {{---}} искомый битовый вектор<br />
<br />
*<tex>\mathtt{numOfBitvector}</tex> {{---}} номер искомого вектора среди всех битовых векторов<br />
<br />
*<tex>\mathtt{pow(2, n)}</tex> {{---}} <tex>2^{n}</tex> количество битовых векторов длины <tex>n</tex><br />
'''function''' num2bitvector(numOfBitvector: '''int''')<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' numOfBitvector >= pow(2, (n-i))<br />
numOfBitvector -= pow(2, (n-i))<br />
bitvector[i] = 1<br />
'''else'''<br />
bitvector[i] = 0 <br />
'''return''' bitvecor <br />
Данный алгоритм работает за <tex>O(n)</tex>, так как в случае битовых векторов <tex>k</tex> не зависит от <tex>n</tex>. <br />
== См. также ==<br />
*[[Получение номера по объекту|Получение номера по объекту]]<br />
<br />
== Источники информации ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31 - ISBN 5-94774-010-9<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D0%B0_%D0%BF%D0%BE_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D1%83&diff=42024Получение объекта по номеру2014-12-10T13:48:09Z<p>Dima32ml: /* Описание алгоритма */</p>
<hr />
<div>== Описание алгоритма ==<br />
Получаем элементы объекта по порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы нашли первые <tex>i</tex> элементов объекта. Для всех вариантов элемента, который может стоять на позиции с номером <tex>i+1</tex>, посчитаем диапазон номеров, который будет соответствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должен стоять на месте с номером <tex>i+1</tex>. Диапазоны номеров не пересекаются, значит на это место больше нельзя поставить никакой другой элемент.<br />
<br />
*В начале каждого шага <tex>\mathtt{numOfObject}</tex> {{---}} номер нужного объекта среди тех, у которых префикс до <tex>i</tex>-го элемента лексикографически равен префиксу нашего объекта. <br />
<br />
*<tex>\mathtt{n}</tex> {{---}} количество мест в комбинаторном объекте (например, битовый вектор длины <tex>n</tex>)<br />
<br />
*<tex>\mathtt{k}</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2</tex>, поскольку возможны только <tex>0</tex> и <tex>1</tex>. Все элементы занумерованы в лексикографическом порядке, начиная с <tex>1</tex>.<br />
Комбинаторные объекты занумерованы с <tex>0</tex>. Переход к нумерации с единицы можно сделать с помощью одной операции декремента перед проходом алгоритма. <br />
'''function''' num2object(numOfObject: '''int''')<br />
'''for''' i = 1 '''to''' n <br />
'''for''' j = 1 '''to''' k <br />
'''if''' j-й элемент можно поставить на i-e место <br />
'''if''' numOfObject >= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i)<br />
numOfObject -= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i)<br />
'''else'''<br />
object[i] = j <br />
'''return''' object<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью. <br />
Приведем примеры получения некоторых [[Комбинаторные объекты|комбинаторных объектов]] по номеру.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения <tex>k</tex>-ой в [[Лексикографический порядок|лексикографическом порядке]] перестановки размера <tex>n</tex>.<br />
Заметим, что всем префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество всевозможных суффиксов зависит только от длины) то есть можем просто посчитать "количество диапазонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>:<br />
<br />
*<tex>\mathtt{k}</tex> {{---}} номер искомой последовательности<br />
<br />
*<tex>\mathtt{n!}</tex> {{---}} количество перестановок размера <tex>n</tex>.<br />
<br />
*<tex>\mathtt{permutation[n]}</tex> {{---}} искомая перестановка.<br />
<br />
*<tex>\mathtt{was[n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
На <tex>i</tex>-ом шаге:<br />
<br />
*<tex>\mathtt{alreadyWas}</tex> {{---}} сколько цифр уже полностью заняты перестановками с меньшим номером.<br />
<br />
*мы должны поставить ту цифру, которая еще полностью не занята, то есть цифру с номером <tex>alreadyWas + 1</tex>. Среди цифр, которых еще нет в нашем префиксе, считаем, что это цифра <tex>j</tex>.<br />
<br />
На <tex>j</tex>-ом шаге:<br />
<br />
*<tex>\mathtt{curFree}</tex> {{---}} если элемент с номером <tex>j</tex> свободен, то он имеет номер curFree среди всех свободных элементов с <tex>1</tex> по <tex>j</tex><br />
'''function''' num2permutation(k: '''int''')<br />
'''for''' i = 1 '''to''' n '''do''' <br />
alreadyWas = k div (n-i)! <br />
k = k mod (n-i)!<br />
curFree = 0<br />
'''for''' j = 1 '''to''' n <br />
'''if''' was[j] == false <br />
curFree++<br />
'''if''' curFree == alreadyWas + 1<br />
permutation[i] = j<br />
was[j] = true<br />
'''return''' permutation<br />
<br />
Данный алгоритм работает за <tex>O(n^2)</tex>, так как в случае перестановок <tex>n=k</tex>. Мы можем посчитать все <tex>n!</tex> за <tex>O(n) </tex>. Асимптотику можно улучшить <br />
до <tex>O(n \log {n}) </tex>, если использовать структуры данных (например, [[Декартово дерево|декартово дерево]] по неявному ключу), которые позволяют искать <tex>i</tex>-й элемент множества и удалять элемент <br />
множества за <tex>O( \log {n}) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения <tex>k</tex>-ого в лексикографическом порядке битового вектора размера <tex>n</tex>.<br />
При построении битовых векторов можно не проверять условие возможности постановки какого-то объекта на текущее место. На каждый позиции может стоять один из двух элементов, независимо от того, какие элементы находятся в префиксе. Так как у нас всего два возможных элемента, упростим второй цикл до условия: <br />
<br />
*<tex>\mathtt{bitvector[n]}</tex> {{---}} искомый битовый вектор<br />
<br />
*<tex>\mathtt{numOfBitvector}</tex> {{---}} номер искомого вектора среди всех битовых векторов<br />
<br />
*<tex>\mathtt{pow(2, n)}</tex> {{---}} <tex>2^{n}</tex> количество битовых векторов длины <tex>n</tex><br />
'''function''' num2bitvector(numOfBitvector: '''int''')<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' numOfBitvector >= pow(2, (n-i))<br />
numOfBitvector -= pow(2, (n-i))<br />
bitvector[i] = 1<br />
'''else'''<br />
bitvector[i] = 0 <br />
'''return''' bitvecor <br />
Данный алгоритм работает за <tex>O(n)</tex>, так как в случае битовых векторов <tex>k</tex> не зависит от <tex>n</tex>. <br />
== См. также ==<br />
*[[Получение номера по объекту|Получение номера по объекту]]<br />
<br />
== Источники информации ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31 - ISBN 5-94774-010-9<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D0%B0_%D0%BF%D0%BE_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D1%83&diff=42023Получение объекта по номеру2014-12-10T13:39:38Z<p>Dima32ml: </p>
<hr />
<div>== Описание алгоритма ==<br />
Получаем элементы объекта по порядку: сначала определим какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы нашли первые <tex>i</tex> элементов объекта. Для всех вариантов элемента, который может стоять на позиции с номером <tex>i+1</tex>, посчитаем диапазон номеров, который будет соответствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должен стоять на месте с номером <tex>i+1</tex>. Диапазоны номеров не пересекаются, значит на это место больше нельзя поставить никакой другой элемент.<br />
<br />
*В начале каждого шага <tex>\mathtt{numOfObject}</tex> {{---}} номер нужного объекта среди тех, у которых префикс до <tex>i</tex>-го элемента лексикографически равен префиксу нашего объекта. <br />
<br />
*<tex>\mathtt{n}</tex> {{---}} количество мест в комбинаторном объекте (например, битовый вектор длины <tex>n</tex>)<br />
<br />
*<tex>\mathtt{k}</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2</tex>, поскольку возможны только <tex>0</tex> и <tex>1</tex>. Все элементы занумерованы в лексикографическом порядке, начиная с <tex>1</tex>.<br />
Комбинаторные объекты занумерованы с <tex>0</tex>. Переход к нумерации с единицы можно сделать с помощью одной операции декремента перед проходом алгоритма. <br />
'''function''' num2object(numOfObject: '''int''')<br />
'''for''' i = 1 '''to''' n <br />
'''for''' j = 1 '''to''' k <br />
'''if''' j-й элемент можно поставить на i-e место <br />
'''if''' numOfObject >= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i)<br />
numOfObject -= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i)<br />
'''else'''<br />
object[i] = j <br />
'''return''' object<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью. <br />
Приведем примеры получения некоторых [[Комбинаторные объекты|комбинаторных объектов]] по номеру.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения <tex>k</tex>-ой в [[Лексикографический порядок|лексикографическом порядке]] перестановки размера <tex>n</tex>.<br />
Заметим, что всем префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество всевозможных суффиксов зависит только от длины) то есть можем просто посчитать "количество диапазонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>:<br />
<br />
*<tex>\mathtt{k}</tex> {{---}} номер искомой последовательности<br />
<br />
*<tex>\mathtt{n!}</tex> {{---}} количество перестановок размера <tex>n</tex>.<br />
<br />
*<tex>\mathtt{permutation[n]}</tex> {{---}} искомая перестановка.<br />
<br />
*<tex>\mathtt{was[n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
На <tex>i</tex>-ом шаге:<br />
<br />
*<tex>\mathtt{alreadyWas}</tex> {{---}} сколько цифр уже полностью заняты перестановками с меньшим номером.<br />
<br />
*мы должны поставить ту цифру, которая еще полностью не занята, то есть цифру с номером <tex>alreadyWas + 1</tex>. Среди цифр, которых еще нет в нашем префиксе, считаем, что это цифра <tex>j</tex>.<br />
<br />
На <tex>j</tex>-ом шаге:<br />
<br />
*<tex>\mathtt{curFree}</tex> {{---}} если элемент с номером <tex>j</tex> свободен, то он имеет номер curFree среди всех свободных элементов с <tex>1</tex> по <tex>j</tex><br />
'''function''' num2permutation(k: '''int''')<br />
'''for''' i = 1 '''to''' n '''do''' <br />
alreadyWas = k div (n-i)! <br />
k = k mod (n-i)!<br />
curFree = 0<br />
'''for''' j = 1 '''to''' n <br />
'''if''' was[j] == false <br />
curFree++<br />
'''if''' curFree == alreadyWas + 1<br />
permutation[i] = j<br />
was[j] = true<br />
'''return''' permutation<br />
<br />
Данный алгоритм работает за <tex>O(n^2)</tex>, так как в случае перестановок <tex>n=k</tex>. Мы можем посчитать все <tex>n!</tex> за <tex>O(n) </tex>. Асимптотику можно улучшить <br />
до <tex>O(n \log {n}) </tex>, если использовать структуры данных (например, [[Декартово дерево|декартово дерево]] по неявному ключу), которые позволяют искать <tex>i</tex>-й элемент множества и удалять элемент <br />
множества за <tex>O( \log {n}) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения <tex>k</tex>-ого в лексикографическом порядке битового вектора размера <tex>n</tex>.<br />
При построении битовых векторов можно не проверять условие возможности постановки какого-то объекта на текущее место. На каждый позиции может стоять один из двух элементов, независимо от того, какие элементы находятся в префиксе. Так как у нас всего два возможных элемента, упростим второй цикл до условия: <br />
<br />
*<tex>\mathtt{bitvector[n]}</tex> {{---}} искомый битовый вектор<br />
<br />
*<tex>\mathtt{numOfBitvector}</tex> {{---}} номер искомого вектора среди всех битовых векторов<br />
<br />
*<tex>\mathtt{pow(2, n)}</tex> {{---}} <tex>2^{n}</tex> количество битовых векторов длины <tex>n</tex><br />
'''function''' num2bitvector(numOfBitvector: '''int''')<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' numOfBitvector >= pow(2, (n-i))<br />
numOfBitvector -= pow(2, (n-i))<br />
bitvector[i] = 1<br />
'''else'''<br />
bitvector[i] = 0 <br />
'''return''' bitvecor <br />
Данный алгоритм работает за <tex>O(n)</tex>, так как в случае битовых векторов <tex>k</tex> не зависит от <tex>n</tex>. <br />
== См. также ==<br />
*[[Получение номера по объекту|Получение номера по объекту]]<br />
<br />
== Источники информации ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31 - ISBN 5-94774-010-9<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D0%B0_%D0%BF%D0%BE_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D1%83&diff=42022Получение объекта по номеру2014-12-10T13:21:43Z<p>Dima32ml: /* Описание алгоритма */</p>
<hr />
<div>== Описание алгоритма ==<br />
Получаем элементы объекта по порядку: сначала определим какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы нашли первые <tex>i</tex> элементов объекта. Для всех вариантов элемента, который может стоять на позиции с номером <tex>i+1</tex>, посчитаем диапазон номеров, который будет соответствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должен стоять на месте с номером <tex>i+1</tex>. Диапазоны номеров не пересекаются, значит на это место больше нельзя поставить никакой другой элемент.<br />
<br />
*В начале каждого шага <tex>\mathtt{numOfObject}</tex> {{---}} номер нужного объекта среди тех, у которых префикс до <tex>i</tex>-го элемента лексикографически равен префиксу нашего объекта. <br />
<br />
*<tex>\mathtt{n}</tex> {{---}} количество мест в комбинаторном объекте (например, битовый вектор длины <tex>n</tex>)<br />
<br />
*<tex>\mathtt{k}</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2</tex>, поскольку возможны только <tex>0</tex> и <tex>1</tex>. Все элементы занумерованы в лексикографическом порядке, начиная с <tex>1</tex>.<br />
Комбинаторные объекты занумерованы с <tex>0</tex>. Переход к нумерации с единицы можно сделать с помощью одной операции декремента перед проходом алгоритма. <br />
'''function''' num2object(numOfObject: '''int''')<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''for''' j = 1 '''to''' k '''do''' <br />
'''if''' j-ый элемент можно поставить на i-e место <br />
'''if''' numOfObject >= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i)<br />
numOfObject -= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i)<br />
'''else'''<br />
object[i] = j <br />
'''return''' object<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью. <br />
Приведем примеры получения некоторых [[Комбинаторные объекты|комбинаторных объектов]] по номеру.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения <tex>k</tex>-ой в [[Лексикографический порядок|лексикографическом порядке]] перестановки размера <tex>n</tex>.<br />
Заметим, что всем префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество всевозможных суффиксов зависит только от длины) то есть можем просто посчитать "количество диапазонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>:<br />
<br />
*k {{---}} номер искомой последовательности<br />
<br />
*n! {{---}} количество перестановок размера <tex>n</tex>.<br />
<br />
*permutation[n] {{---}} искомая перестановка.<br />
<br />
*was[n] {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
На <tex>i</tex>-ом шаге:<br />
<br />
*alreadyWas {{---}} сколько цифр уже полностью заняты перестановками с меньшим номером.<br />
<br />
*мы должны поставить ту цифру, которая еще полностью не занята, то есть цифру с номером alreadyWas + 1. Среди цифр, которых еще нет в нашем префиксе, считаем, что это цифра j.<br />
<br />
На <tex>j</tex>-ом шаге:<br />
<br />
*curFree {{---}} если элемент с номером <tex>j</tex> свободен, то он имеет номер curFree среди всех свободных элементов с 1 по <tex>j</tex><br />
'''function''' num2permutation(k: '''int''')<br />
'''for''' i = 1 '''to''' n '''do''' <br />
alreadyWas = k div (n-i)! <br />
k = k mod (n-i)!<br />
curFree = 0<br />
'''for''' j = 1 '''to''' n <br />
'''if''' was[j] == false <br />
curFree++<br />
'''if''' curFree == alreadyWas + 1<br />
permutation[i] = j<br />
was[j] = true<br />
'''return''' permutation<br />
<br />
Данный алгоритм работает за <tex>O(n^2)</tex>, так как в случае перестановок <tex>n=k</tex>. Мы можем посчитать все n! за <tex>O(n) </tex>. Асимптотику можно улучшить <br />
до <tex>O(n \log {n}) </tex>, если использовать структуры данных (например, [[Декартово дерево|декартово дерево]] по неявному ключу), которые позволяют искать <tex>i</tex>-ый элемент множества и удалять элемент <br />
множества за <tex>O( \log {n}) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения <tex>k</tex>-ого в лексикографическом порядке битового вектора размера <tex>n</tex>.<br />
При построении битовых векторов можно не проверять условие возможности постановки какого-то объекта на текущее место. На каждый позиции может стоять один из двух элементов, независимо от того, какие элементы находятся в префиксе. Так как у нас всего два возможных элемента, упростим второй цикл до условия: <br />
<br />
*bitvector[n] {{---}} искомый битовый вектор<br />
<br />
*numOfBitvector {{---}} номер искомого вектора среди всех битовых векторов<br />
<br />
*pow(2, n) {{---}} <tex>2^{n}</tex> количество битовых векторов длины <tex>n</tex><br />
'''function''' num2bitvector(numOfBitvector: '''int''')<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' numOfBitvector >= pow(2, (n-i))<br />
numOfBitvector -= pow(2, (n-i))<br />
bitvector[i] = 1<br />
'''else'''<br />
bitvector[i] = 0 <br />
'''return''' bitvecor <br />
Данный алгоритм работает за <tex>O(n)</tex>, так как в случае битовых векторов <tex>k</tex> не зависит от <tex>n</tex>. <br />
== См. также ==<br />
*[[Получение номера по объекту|Получение номера по объекту]]<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31 - ISBN 5-94774-010-9<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41889Получение номера по объекту2014-12-06T13:04:36Z<p>Dima32ml: /* Описание алгоритма */</p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>(i+1)</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму:<br />
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из числовых представлений лексикографически упорядоченных элементов множества <tex>A</tex>,<br />
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,<br />
<br />
'''int''' object2num(a: '''list<A>'''):<br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = 1 '''to''' a[i] - 1 <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск элементов меньше рассматриваемого можно упростить до проверки элемента на равенство <tex>1</tex>: <br />
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,<br />
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,<br />
<br />
'''int''' bitvector2num(bitvector: '''list<int>'''):<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += <tex>2^{n-i}</tex><br />
'''return''' numOfBitvector<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,<br />
*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,<br />
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,<br />
<br />
'''int''' permutation2num(a: '''list<int>'''):<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = ''true'' <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex> и <tex>O(n) </tex> для предподсчёта.<br />
<br />
== Сочетания ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex dpi=140>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex dpi=140>$$\sum\limits^{val_1-1}_{i=1} {\binom{n-i}{k-1}}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex dpi=140>$$\sum\limits^{val_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}$$</tex>. Аналогично продолжаем по следующим позициям:<br />
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,<br />
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,<br />
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,<br />
<br />
'''int''' choose2num(choose: '''list<int>'''):<br />
numOfChoose = 0<br />
'''for''' i = 1 '''to''' K <br />
'''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1<br />
numOfChoose += C[N - j][K - i]<br />
'''return''' numOfChoose<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex> и <tex>O(K \cdot N) </tex> для предподсчёта.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Получение следующего объекта|Получение следующего объекта]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Источники информации ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41888Получение номера по объекту2014-12-06T13:03:30Z<p>Dima32ml: /* Описание алгоритма */</p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму:<br />
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из числовых представлений лексикографически упорядоченных элементов множества <tex>A</tex>,<br />
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,<br />
<br />
'''int''' object2num(a: '''list<A>'''):<br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = 1 '''to''' a[i] - 1 <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск элементов меньше рассматриваемого можно упростить до проверки элемента на равенство <tex>1</tex>: <br />
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,<br />
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,<br />
<br />
'''int''' bitvector2num(bitvector: '''list<int>'''):<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += <tex>2^{n-i}</tex><br />
'''return''' numOfBitvector<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,<br />
*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,<br />
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,<br />
<br />
'''int''' permutation2num(a: '''list<int>'''):<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = ''true'' <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex> и <tex>O(n) </tex> для предподсчёта.<br />
<br />
== Сочетания ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex dpi=140>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex dpi=140>$$\sum\limits^{val_1-1}_{i=1} {\binom{n-i}{k-1}}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex dpi=140>$$\sum\limits^{val_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}$$</tex>. Аналогично продолжаем по следующим позициям:<br />
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,<br />
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,<br />
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,<br />
<br />
'''int''' choose2num(choose: '''list<int>'''):<br />
numOfChoose = 0<br />
'''for''' i = 1 '''to''' K <br />
'''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1<br />
numOfChoose += C[N - j][K - i]<br />
'''return''' numOfChoose<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex> и <tex>O(K \cdot N) </tex> для предподсчёта.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Получение следующего объекта|Получение следующего объекта]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Источники информации ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41887Получение номера по объекту2014-12-06T12:59:03Z<p>Dima32ml: /* Битовые вектора */</p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму:<br />
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из числовых представлений лексикографически упорядоченных элементов множества <tex>A</tex>,<br />
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,<br />
<br />
'''int''' object2num(a: '''list<A>'''):<br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = 1 '''to''' a[i] - 1 <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск элементов меньше рассматриваемого можно упростить до проверки элемента на равенство <tex>1</tex>: <br />
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,<br />
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,<br />
<br />
'''int''' bitvector2num(bitvector: '''list<int>'''):<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += <tex>2^{n-i}</tex><br />
'''return''' numOfBitvector<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,<br />
*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,<br />
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,<br />
<br />
'''int''' permutation2num(a: '''list<int>'''):<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = ''true'' <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex> и <tex>O(n) </tex> для предподсчёта.<br />
<br />
== Сочетания ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex dpi=140>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex dpi=140>$$\sum\limits^{val_1-1}_{i=1} {\binom{n-i}{k-1}}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex dpi=140>$$\sum\limits^{val_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}$$</tex>. Аналогично продолжаем по следующим позициям:<br />
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,<br />
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,<br />
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,<br />
<br />
'''int''' choose2num(choose: '''list<int>'''):<br />
numOfChoose = 0<br />
'''for''' i = 1 '''to''' K <br />
'''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1<br />
numOfChoose += C[N - j][K - i]<br />
'''return''' numOfChoose<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex> и <tex>O(K \cdot N) </tex> для предподсчёта.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Получение следующего объекта|Получение следующего объекта]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Источники информации ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41886Получение номера по объекту2014-12-06T12:50:51Z<p>Dima32ml: </p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму:<br />
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из числовых представлений лексикографически упорядоченных элементов множества <tex>A</tex>,<br />
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,<br />
<br />
'''int''' object2num(a: '''list<A>'''):<br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = 1 '''to''' a[i] - 1 <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск элементов меньше рассматриваемого можно упростить до проверки элемента на равенство <tex>1</tex>: <br />
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,<br />
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,<br />
<br />
'''int''' bitvector2num(bitvector: '''list<int>'''):<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,<br />
*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,<br />
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,<br />
<br />
'''int''' permutation2num(a: '''list<int>'''):<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = ''true'' <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex> и <tex>O(n) </tex> для предподсчёта.<br />
<br />
== Сочетания ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex dpi=140>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex dpi=140>$$\sum\limits^{val_1-1}_{i=1} {\binom{n-i}{k-1}}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex dpi=140>$$\sum\limits^{val_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}$$</tex>. Аналогично продолжаем по следующим позициям:<br />
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,<br />
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,<br />
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,<br />
<br />
'''int''' choose2num(choose: '''list<int>'''):<br />
numOfChoose = 0<br />
'''for''' i = 1 '''to''' K <br />
'''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1<br />
numOfChoose += C[N - j][K - i]<br />
'''return''' numOfChoose<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex> и <tex>O(K \cdot N) </tex> для предподсчёта.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Получение следующего объекта|Получение следующего объекта]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Источники информации ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41884Получение номера по объекту2014-12-05T23:32:04Z<p>Dima32ml: </p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму:<br />
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>,<br />
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,<br />
<br />
'''int''' object2num(a: '''list<A>'''):<br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = <tex>A_{min}</tex> '''to''' предшествующий a[i] элемент '''do''' <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {---} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск элементов меньше рассматриваемого можно упростить до проверки элемента на равенство <tex>1</tex>: <br />
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,<br />
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,<br />
<br />
'''int''' bitvector2num(bitvector: '''list<int>'''):<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += 2 <tex>\ll</tex> n-i-1<br />
'''return''' numOfBitvector<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,<br />
*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,<br />
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,<br />
<br />
'''int''' permutation2num(a: '''list<int>'''):<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = ''true'' <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex> и <tex>O(n) </tex> для предподсчёта.<br />
<br />
== Сочетания ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex>$$\sum\limits^{val_1-1}_{i=1} {\binom{n-i}{k-1}}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex>$$\sum\limits^{val_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}$$</tex>. Аналогично продолжаем по следующим позициям:<br />
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,<br />
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,<br />
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,<br />
<br />
'''int''' choose2num(choose: '''list<int>'''):<br />
numOfChoose = 0<br />
'''for''' i = 1 '''to''' K '''do''' <br />
'''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1 '''do'''<br />
numOfChoose += C[N - j][K - i]<br />
'''return''' numOfChoose<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex> и <tex>O(K \cdot N) </tex> для предподсчёта.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Получение следующего объекта|Получение следующего объекта]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Источники информации ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41883Получение номера по объекту2014-12-05T23:24:37Z<p>Dima32ml: </p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму:<br />
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>,<br />
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,<br />
<br />
'''int''' object2num(a: '''list<A>'''):<br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = <tex>A_{min}</tex> '''to''' предшествующий a[i] элемент '''do''' <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {---} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до проверки элемента на равенство <tex>1</tex>: <br />
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,<br />
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,<br />
<br />
'''int''' bitvector2num(bitvector: '''list<int>'''):<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += 2 <tex>\ll</tex> n-i-1<br />
'''return''' numOfBitvector<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,<br />
*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,<br />
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,<br />
<br />
'''int''' permutation2num(a: '''list<int>'''):<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = ''true'' <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex> и <tex>O(n) </tex> для предподсчёта.<br />
<br />
== Сочетания ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex>$$\sum_{i=1}^{val_1-1} \binom{n-i}{k-1}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex>$$\sum_{i=val_1+1}^{val_2-1} \binom{n-i}{k-2}$$</tex>. Аналогично продолжаем по следующим позициям:<br />
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,<br />
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,<br />
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,<br />
<br />
'''int''' choose2num(choose: '''list<int>'''):<br />
numOfChoose = 0<br />
'''for''' i = 1 '''to''' K '''do''' <br />
'''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1 '''do'''<br />
numOfChoose += C[N - j][K - i]<br />
'''return''' numOfChoose<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex> и <tex>O(K \cdot N) </tex> для предподсчёта.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Получение следующего объекта|Получение следующего объекта]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Источники информации ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41882Получение номера по объекту2014-12-05T22:59:38Z<p>Dima32ml: </p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму:<br />
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>,<br />
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,<br />
<br />
'''int''' object2num(a: '''list<A>'''):<br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = <tex>A_{min}</tex> '''to''' предшествующий a[i] элемент '''do''' <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {---} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до проверки элемента на равенство <tex>1</tex>: <br />
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,<br />
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,<br />
<br />
'''int''' bitvector2num(bitvector: '''list<int>'''):<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,<br />
*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,<br />
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,<br />
<br />
'''int''' permutation2num(a: '''list<int>'''):<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = ''true'' <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex>.<br />
<br />
== Сочетания ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex>$$\sum_{i=1}^{val_1-1} \binom{n-i}{k-1}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex>$$\sum_{i=val_1+1}^{val_2-1} \binom{n-i}{k-2}$$</tex>. Аналогично продолжаем по следующим позициям:<br />
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,<br />
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,<br />
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,<br />
<br />
'''int''' choose2num(choose: '''list<int>'''):<br />
numOfChoose = 0<br />
'''for''' i = 1 '''to''' K '''do''' <br />
'''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1 '''do'''<br />
numOfChoose += C[N - j][K - i]<br />
'''return''' numOfChoose<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex>.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Получение следующего объекта|Получение следующего объекта]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Источники информации ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41881Получение номера по объекту2014-12-05T22:23:40Z<p>Dima32ml: </p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму:<br />
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>,<br />
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,<br />
<br />
'''int''' object2num(a: '''list<A>'''):<br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = <tex>A_{min}</tex> '''to''' предшествующий элемент '''do''' <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {---} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,<br />
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,<br />
<br />
'''int''' bitvector2num(bitvector: '''list<int>'''):<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,<br />
*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,<br />
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,<br />
<br />
'''int''' permutation2num(a: '''list<int>'''):<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = ''true'' <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex>.<br />
<br />
== Сочетания ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex>$$\sum_{i=1}^{val_1-1} \binom{n-i}{k-1}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex>$$\sum_{i=val_1+1}^{val_2-1} \binom{n-i}{k-2}$$</tex>. Аналогично продолжаем по следующим позициям:<br />
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,<br />
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,<br />
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,<br />
<br />
'''int''' choose2num(choose: '''list<int>'''):<br />
numOfChoose = 0<br />
'''for''' i = 1 '''to''' K '''do''' <br />
'''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1 '''do'''<br />
numOfChoose += C[N - j][K - i]<br />
'''return''' numOfChoose<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex>.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Литература ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41880Получение номера по объекту2014-12-05T22:22:52Z<p>Dima32ml: </p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму:<br />
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>,<br />
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,<br />
<br />
'''int''' object2num(a: '''list<A>'''):<br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = <tex>A_{min}</tex> '''to''' предшествующий элемент '''do''' <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {---} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,<br />
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,<br />
<br />
'''int''' bitvector2num(bitvector: '''list<int>'''):<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,<br />
*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,<br />
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,<br />
<br />
'''int''' permutation2num(a: '''list<int>'''):<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = ''true'' <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex>.<br />
<br />
== Сочетания ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex>$$\sum_{i=1}^{val_1-1} \binom{n-i}{k-1}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex>$$\sum_{i=val_1+1}^{val_2-1} \binom{n-i}{k-2}$$</tex>. Аналогично продолжаем по следующим позициям:<br />
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,<br />
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,<br />
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,<br />
<br />
<font color=green>// Нумерация сочетаний с <tex>0</tex></font> <br />
'''int''' choose2num(choose: '''list<int>'''):<br />
numOfChoose = 0<br />
'''for''' i = 1 '''to''' K '''do''' <br />
'''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1 '''do'''<br />
numOfChoose += C[N - j][K - i]<br />
'''return''' numOfChoose<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex>.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Литература ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41879Получение номера по объекту2014-12-05T22:22:08Z<p>Dima32ml: </p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму:<br />
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>,<br />
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,<br />
<br />
'''int''' object2num(a: '''list<A>'''):<br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = <tex>A_{min}</tex> '''to''' предшествующий элемент '''do''' <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {---} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,<br />
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,<br />
<br />
'''int''' bitvector2num(bitvector: '''list<int>'''):<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,<br />
*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,<br />
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,<br />
<br />
'''int''' permutation2num(a: '''list<int>'''):<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = ''true'' <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex>.<br />
<br />
== Сочетания ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex>$$\sum_{i=1}^{val_1-1} \binom{n-i}{k-1}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex>$$\sum_{i=val_1+1}^{val_2-1} \binom{n-i}{k-2}$$</tex>. Аналогично продолжаем по следующим позициям:<br />
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,<br />
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,<br />
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,<br />
<br />
<font color=green>// Нумерация сочетаний с <tex>0</tex></font> <br />
'''int''' choose2num(choose: '''list<int>'''):<br />
numOfChoose = 0<br />
'''for''' i = 1 '''to''' K '''do''' <br />
'''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1 '''do'''<br />
numOfChoose += C[N - j][K - i]<br />
'''return''' numOfChoose<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex>.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Литература ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41878Получение номера по объекту2014-12-05T22:20:45Z<p>Dima32ml: </p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму:<br />
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>,<br />
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,<br />
<br />
'''int''' object2num(a: '''list<A>'''):<br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = <tex>A_{min}</tex> '''to''' предшествующий элемент '''do''' <font color=green>// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {---} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,<br />
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,<br />
<br />
'''int''' bitvector2num(bitvector: '''list<int>'''):<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,<br />
*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,<br />
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,<br />
<br />
'''int''' permutation2num(a: '''list<int>'''):<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = ''true'' <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex>.<br />
<br />
== Сочетания ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex>$$\sum_{i=1}^{val_1-1} \binom{n-i}{k-1}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex>$$\sum_{i=val_1+1}^{val_2-1} \binom{n-i}{k-2}$$</tex>. Аналогично продолжаем по следующим позициям:<br />
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,<br />
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,<br />
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,<br />
<br />
<font color=green>// Нумерация сочетаний с <tex>0</tex></font> <br />
'''int''' choose2num(choose: '''list<int>'''):<br />
numOfChoose = 0<br />
'''for''' i = 1 '''to''' K '''do''' <br />
'''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1 '''do'''<br />
numOfChoose += C[N - j][K - i]<br />
'''return''' numOfChoose<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex>.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Литература ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41877Получение номера по объекту2014-12-05T22:20:17Z<p>Dima32ml: </p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму:<br />
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>,<br />
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,<br />
<br />
'''int''' object2num(a: '''list<A>'''):<br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = <tex>A_{min}</tex> '''to''' предшествующий элемент '''do''' <font color=green>// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {---} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,<br />
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,<br />
<br />
'''int''' bitvector2num(bitvector: '''list<int>'''):<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,<br />
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,<br />
*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,<br />
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,<br />
<br />
'''int''' permutation2num(a: '''list<int>'''):<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> {---} количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = ''true'' <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex>.<br />
<br />
== Сочетания ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex>$$\sum_{i=1}^{val_1-1} \binom{n-i}{k-1}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex>$$\sum_{i=val_1+1}^{val_2-1} \binom{n-i}{k-2}$$</tex>. Аналогично продолжаем по следующим позициям:<br />
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,<br />
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,<br />
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,<br />
<br />
<font color=green>// Нумерация сочетаний с <tex>0</tex></font> <br />
'''int''' choose2num(choose: '''list<int>'''):<br />
numOfChoose = 0<br />
'''for''' i = 1 '''to''' K '''do''' <br />
'''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1 '''do'''<br />
numOfChoose += C[N - j][K - i]<br />
'''return''' numOfChoose<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex>.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Литература ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41876Получение номера по объекту2014-12-05T20:42:34Z<p>Dima32ml: /* Сочетания */</p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму<br />
*<tex>numOfObject</tex> {{---}} искомый номер комбинаторного объекта.<br />
*<tex>a[1..n]</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.<br />
*<tex>d[i][j]</tex> {{---}} (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)<br />
<br />
'''int''' object2num(a: '''list <A>''') <br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.<br />
*<tex>P[1..n]</tex> {{---}} количество перестановок данного размера.<br />
*<tex>a[1..n]</tex> {{---}} данная перестановка.<br />
*<tex>was[1..n]</tex> {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
'''int''' permutation2num(a: '''list <int>''')<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> - количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == false <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = true <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex>.<br />
<br />
== Сочетания ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex>C_n^k</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex>$$\sum_{i=1}^{val_1-1} C_{n-i}^{k-1}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex>$$\sum_{i=val_1+1}^{val_2-1} C_{n-i}^{k-2}$$</tex>. Аналогично продолжаем по следующим позициям:<br />
*<tex>numOfChoose</tex> {{---}} искомый номер сочетания.<br />
*<tex>choose[1..K]</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>choose[0] = 0</tex>.<br />
*<tex>C[n][k]</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>C[n][0] = 1</tex>.<br />
<br />
<font color=green>// Нумерация сочетаний с <tex>0</tex></font> <br />
'''int''' choose2num(choose: '''list <int>''')<br />
numOfChoose = 0<br />
'''for''' i = 1 '''to''' K '''do''' <br />
'''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1 '''do'''<br />
numOfChoose += C[N - j][K - i]<br />
'''return''' numOfChoose<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера<tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>numOfBitvector</tex> {{---}} искомый номер вектора.<br />
*<tex>bitvector[1..n]</tex> {{---}} данный вектор.<br />
<br />
'''int''' bitvector2num(bitvector: '''list <int>''')<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Литература ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41875Получение номера по объекту2014-12-05T20:29:22Z<p>Dima32ml: /* Литература */</p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму<br />
*<tex>numOfObject</tex> {{---}} искомый номер комбинаторного объекта.<br />
*<tex>a[1..n]</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.<br />
*<tex>d[i][j]</tex> {{---}} (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)<br />
<br />
'''int''' object2num(a: '''list <A>''') <br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.<br />
*<tex>P[1..n]</tex> {{---}} количество перестановок данного размера.<br />
*<tex>a[1..n]</tex> {{---}} данная перестановка.<br />
*<tex>was[1..n]</tex> {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
'''int''' permutation2num(a: '''list <int>''')<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> - количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == false <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = true <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex>.<br />
<br />
== Сочетания ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex>C_n^k</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex>$$\sum_{i=1}^{val_1-1} C_{n-i}^{k-1}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex>$$\sum_{i=val_1+1}^{val_2-1} C_{n-i}^{k-2}$$</tex>. Аналогично продолжаем по следующим позициям:<br />
*<tex>numOfChoose</tex> {{---}} искомый номер сочетания.<br />
*<tex>choose[1..K]</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, <tex>choose[0] = 0</tex>.<br />
*<tex>C[n][k]</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>C[n][0] = 1</tex>.<br />
<br />
<font color=green>// Нумерация сочетаний с <tex>0</tex></font> <br />
'''int''' choose2num(choose: '''list <int>''')<br />
numOfChoose = 0<br />
'''for''' i = 1 '''to''' K '''do''' <br />
'''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1 '''do'''<br />
numOfChoose += C[N - j][K - i]<br />
'''return''' numOfChoose<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера<tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>numOfBitvector</tex> {{---}} искомый номер вектора.<br />
*<tex>bitvector[1..n]</tex> {{---}} данный вектор.<br />
<br />
'''int''' bitvector2num(bitvector: '''list <int>''')<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Литература ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41874Получение номера по объекту2014-12-05T20:02:30Z<p>Dima32ml: </p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму<br />
*<tex>numOfObject</tex> {{---}} искомый номер комбинаторного объекта.<br />
*<tex>a[1..n]</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.<br />
*<tex>d[i][j]</tex> {{---}} (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)<br />
<br />
'''int''' object2num(a: '''list <A>''') <br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.<br />
*<tex>P[1..n]</tex> {{---}} количество перестановок данного размера.<br />
*<tex>a[1..n]</tex> {{---}} данная перестановка.<br />
*<tex>was[1..n]</tex> {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
'''int''' permutation2num(a: '''list <int>''')<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> - количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == false <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = true <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex>.<br />
<br />
== Сочетания ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex>C_n^k</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex>$$\sum_{i=1}^{val_1-1} C_{n-i}^{k-1}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex>$$\sum_{i=val_1+1}^{val_2-1} C_{n-i}^{k-2}$$</tex>. Аналогично продолжаем по следующим позициям:<br />
*<tex>numOfChoose</tex> {{---}} искомый номер сочетания.<br />
*<tex>choose[1..K]</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, <tex>choose[0] = 0</tex>.<br />
*<tex>C[n][k]</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>C[n][0] = 1</tex>.<br />
<br />
<font color=green>// Нумерация сочетаний с <tex>0</tex></font> <br />
'''int''' choose2num(choose: '''list <int>''')<br />
numOfChoose = 0<br />
'''for''' i = 1 '''to''' K '''do''' <br />
'''for''' i = choose[i - 1] + 1 '''to''' choose[i] - 1 '''do'''<br />
numOfChoose += C[N - j][K - i]<br />
'''return''' numOfChoose<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера<tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>numOfBitvector</tex> {{---}} искомый номер вектора.<br />
*<tex>bitvector[1..n]</tex> {{---}} данный вектор.<br />
<br />
'''int''' bitvector2num(bitvector: '''list <int>''')<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Литература ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41791Получение номера по объекту2014-12-05T00:18:15Z<p>Dima32ml: </p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму<br />
*<tex>numOfObject</tex> {{---}} искомый номер комбинаторного объекта.<br />
*<tex>a[1..n]</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.<br />
*<tex>d[i][j]</tex> - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)<br />
<br />
'''int''' object2num(a: '''list <A>''') <br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.<br />
*<tex>P[1..n]</tex> {{---}} количество перестановок данного размера.<br />
*<tex>a[1..n]</tex> {{---}} данная перестановка.<br />
*<tex>was[1..n]</tex> {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
'''int''' permutation2num(a: '''list <int>''')<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> - количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == false <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = true <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Данный алгоритм работает за <tex>O(n ^ 2) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>numOfBitvector</tex> {{---}} искомый номер вектора.<br />
*<tex>bitvector[1..n]</tex> {{---}} данный вектор.<br />
<br />
'''int''' bitvector2num(bitvector: '''list <int>''')<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Данный алгоритм работает за <tex>O(n) </tex>.<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]<br />
<br />
== Литература ==<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41790Получение номера по объекту2014-12-05T00:07:58Z<p>Dima32ml: /* Битовые вектора */</p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму<br />
*<tex>numOfObject</tex> {{---}} искомый номер комбинаторного объекта.<br />
*<tex>a[1..n]</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.<br />
*<tex>d[i][j]</tex> - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)<br />
<br />
'''int''' object2num(a: '''list <A>''') <br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.<br />
*<tex>P[1..n]</tex> {{---}} количество перестановок данного размера.<br />
*<tex>a[1..n]</tex> {{---}} данная перестановка.<br />
*<tex>was[1..n]</tex> {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
'''int''' permutation2num(a: '''list <int>''')<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> - количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == false <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = true <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Данный алгоритм работает за <tex>O(n ^ 2) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>numOfBitvector</tex> {{---}} искомый номер вектора.<br />
*<tex>bitvector[1..n]</tex> {{---}} данный вектор.<br />
<br />
'''int''' bitvector2num(bitvector: '''list <int>''')<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Данный алгоритм работает за <tex>O(n) </tex>.<br />
<br />
== Скобочные последовательности ==<br />
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8 Получение номера правильной скобочной последоватеьности]<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41789Получение номера по объекту2014-12-05T00:04:30Z<p>Dima32ml: /* Перестановки */</p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму<br />
*<tex>numOfObject</tex> {{---}} искомый номер комбинаторного объекта.<br />
*<tex>a[1..n]</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.<br />
*<tex>d[i][j]</tex> - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)<br />
<br />
'''int''' object2num(a: '''list <A>''') <br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.<br />
*<tex>P[1..n]</tex> {{---}} количество перестановок данного размера.<br />
*<tex>a[1..n]</tex> {{---}} данная перестановка.<br />
*<tex>was[1..n]</tex> {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
'''int''' permutation2num(a: '''list <int>''')<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> - количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == false <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = true <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Данный алгоритм работает за <tex>O(n ^ 2) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>numOfBitvector</tex> {{---}} искомый номер вектора.<br />
*<tex>bitvector[1..n]</tex> {{---}} данный вектор.<br />
<br />
'''function''' bitvector2num(bitvector: '''list <int>''')<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Данный алгоритм работает за <tex>O(n) </tex>.<br />
<br />
== Скобочные последовательности ==<br />
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8 Получение номера правильной скобочной последоватеьности]<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41788Получение номера по объекту2014-12-05T00:03:52Z<p>Dima32ml: /* Описание алгоритма */</p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму<br />
*<tex>numOfObject</tex> {{---}} искомый номер комбинаторного объекта.<br />
*<tex>a[1..n]</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.<br />
*<tex>d[i][j]</tex> - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)<br />
<br />
'''int''' object2num(a: '''list <A>''') <br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.<br />
*<tex>P[1..n]</tex> {{---}} количество перестановок данного размера.<br />
*<tex>a[1..n]</tex> {{---}} данная перестановка.<br />
*<tex>was[1..n]</tex> {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
'''function''' permutation2num(a: '''list <int>''')<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> - количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == false <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = true <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Данный алгоритм работает за <tex>O(n ^ 2) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>numOfBitvector</tex> {{---}} искомый номер вектора.<br />
*<tex>bitvector[1..n]</tex> {{---}} данный вектор.<br />
<br />
'''function''' bitvector2num(bitvector: '''list <int>''')<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Данный алгоритм работает за <tex>O(n) </tex>.<br />
<br />
== Скобочные последовательности ==<br />
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8 Получение номера правильной скобочной последоватеьности]<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41787Получение номера по объекту2014-12-05T00:03:19Z<p>Dima32ml: /* Перестановки */</p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму<br />
*<tex>numOfObject</tex> {{---}} искомый номер комбинаторного объекта.<br />
*<tex>a[1..n]</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.<br />
*<tex>d[i][j]</tex> - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)<br />
<br />
'''int''' object2num(a: '''list <A>''') <br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.<br />
*<tex>P[1..n]</tex> {{---}} количество перестановок данного размера.<br />
*<tex>a[1..n]</tex> {{---}} данная перестановка.<br />
*<tex>was[1..n]</tex> {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
'''function''' permutation2num(a: '''list <int>''')<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// <tex>n</tex> - количество элементов в перестановке</font> <br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> <br />
'''if''' was[j] == false <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> <br />
numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <br />
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> <br />
was[a[i]] = true <font color=green>// <tex>i</tex>-й элемент использован</font> <br />
'''return''' numOfPermutation<br />
<br />
Данный алгоритм работает за <tex>O(n ^ 2) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>numOfBitvector</tex> {{---}} искомый номер вектора.<br />
*<tex>bitvector[1..n]</tex> {{---}} данный вектор.<br />
<br />
'''function''' bitvector2num(bitvector: '''list <int>''')<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Данный алгоритм работает за <tex>O(n) </tex>.<br />
<br />
== Скобочные последовательности ==<br />
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8 Получение номера правильной скобочной последоватеьности]<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41786Получение номера по объекту2014-12-04T23:48:40Z<p>Dima32ml: /* Описание алгоритма */</p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму<br />
*<tex>numOfObject</tex> {{---}} искомый номер комбинаторного объекта.<br />
*<tex>a[1..n]</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.<br />
*<tex>d[i][j]</tex> - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)<br />
<br />
'''int''' object2num(a: '''list <A>''') <br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font><br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' <font color=green>// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого</font><br />
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.<br />
*<tex>P[1..n]</tex> {{---}} количество перестановок данного размера.<br />
*<tex>a[1..n]</tex> {{---}} данная перестановка.<br />
*<tex>was[1..n]</tex> {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
'''function''' permutation2num(a: '''list <int>''')<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' ''// n - количество элементов в перестановке''<br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элемент, лексикографически меньший нашего, который может стоять на i-м месте <br />
'''if''' was[j] == false ''// если элемент j ранее не был использован<br />
'''then''' numOfPermutation += P[n - i] ''// все перестановки с префиксом длиной i-1 равным нашему, и i-й элемент у которых <br />
''меньше нашего в лексикографическом порядке, идут раньше данной перестановки <br />
was[a[i]] = true ''// i-й элемент использован <br />
'''return''' numOfPermutation<br />
<br />
Данный алгоритм работает за <tex>O(n ^ 2) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>numOfBitvector</tex> {{---}} искомый номер вектора.<br />
*<tex>bitvector[1..n]</tex> {{---}} данный вектор.<br />
<br />
'''function''' bitvector2num(bitvector: '''list <int>''')<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Данный алгоритм работает за <tex>O(n) </tex>.<br />
<br />
== Скобочные последовательности ==<br />
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8 Получение номера правильной скобочной последоватеьности]<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41785Получение номера по объекту2014-12-04T23:41:45Z<p>Dima32ml: /* Описание алгоритма */</p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму<br />
*<tex>numOfObject</tex> {{---}} искомый номер комбинаторного объекта.<br />
*<tex>a[1..n]</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.<br />
*<tex>d[i][j]</tex> - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)<br />
<br />
'''int''' object2num(a: '''list <A>''') <br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' ''// перебираем элементы комбинаторного объекта''<br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого'' <br />
'''if''' элемент j можно поставить на i-e место<br />
numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.<br />
*<tex>P[1..n]</tex> {{---}} количество перестановок данного размера.<br />
*<tex>a[1..n]</tex> {{---}} данная перестановка.<br />
*<tex>was[1..n]</tex> {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
'''function''' permutation2num(a: '''list <int>''')<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' ''// n - количество элементов в перестановке''<br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элемент, лексикографически меньший нашего, который может стоять на i-м месте <br />
'''if''' was[j] == false ''// если элемент j ранее не был использован<br />
'''then''' numOfPermutation += P[n - i] ''// все перестановки с префиксом длиной i-1 равным нашему, и i-й элемент у которых <br />
''меньше нашего в лексикографическом порядке, идут раньше данной перестановки <br />
was[a[i]] = true ''// i-й элемент использован <br />
'''return''' numOfPermutation<br />
<br />
Данный алгоритм работает за <tex>O(n ^ 2) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>numOfBitvector</tex> {{---}} искомый номер вектора.<br />
*<tex>bitvector[1..n]</tex> {{---}} данный вектор.<br />
<br />
'''function''' bitvector2num(bitvector: '''list <int>''')<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Данный алгоритм работает за <tex>O(n) </tex>.<br />
<br />
== Скобочные последовательности ==<br />
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8 Получение номера правильной скобочной последоватеьности]<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41783Получение номера по объекту2014-12-04T23:24:19Z<p>Dima32ml: /* Битовые вектора */</p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму<br />
*<tex>numOfObject</tex> {{---}} искомый номер комбинаторного объекта.<br />
*<tex>a[1..n]</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.<br />
*<tex>d[i][j]</tex> - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)<br />
<br />
'''function''' object2num(a: '''list <A>''') <br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' ''// перебираем элементы комбинаторного объекта''<br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого'' <br />
'''if''' элемент j можно поставить на i-e место<br />
'''then''' numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.<br />
*<tex>P[1..n]</tex> {{---}} количество перестановок данного размера.<br />
*<tex>a[1..n]</tex> {{---}} данная перестановка.<br />
*<tex>was[1..n]</tex> {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
'''function''' permutation2num(a: '''list <int>''')<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' ''// n - количество элементов в перестановке''<br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элемент, лексикографически меньший нашего, который может стоять на i-м месте <br />
'''if''' was[j] == false ''// если элемент j ранее не был использован<br />
'''then''' numOfPermutation += P[n - i] ''// все перестановки с префиксом длиной i-1 равным нашему, и i-й элемент у которых <br />
''меньше нашего в лексикографическом порядке, идут раньше данной перестановки <br />
was[a[i]] = true ''// i-й элемент использован <br />
'''return''' numOfPermutation<br />
<br />
Данный алгоритм работает за <tex>O(n ^ 2) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*<tex>numOfBitvector</tex> {{---}} искомый номер вектора.<br />
*<tex>bitvector[1..n]</tex> {{---}} данный вектор.<br />
<br />
'''function''' bitvector2num(bitvector: '''list <int>''')<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
Данный алгоритм работает за <tex>O(n) </tex>.<br />
<br />
== Скобочные последовательности ==<br />
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8 Получение номера правильной скобочной последоватеьности]<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41782Получение номера по объекту2014-12-04T23:19:51Z<p>Dima32ml: /* Перестановки */</p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму<br />
*<tex>numOfObject</tex> {{---}} искомый номер комбинаторного объекта.<br />
*<tex>a[1..n]</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.<br />
*<tex>d[i][j]</tex> - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)<br />
<br />
'''function''' object2num(a: '''list <A>''') <br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' ''// перебираем элементы комбинаторного объекта''<br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого'' <br />
'''if''' элемент j можно поставить на i-e место<br />
'''then''' numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.<br />
*<tex>P[1..n]</tex> {{---}} количество перестановок данного размера.<br />
*<tex>a[1..n]</tex> {{---}} данная перестановка.<br />
*<tex>was[1..n]</tex> {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
'''function''' permutation2num(a: '''list <int>''')<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' ''// n - количество элементов в перестановке''<br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элемент, лексикографически меньший нашего, который может стоять на i-м месте <br />
'''if''' was[j] == false ''// если элемент j ранее не был использован<br />
'''then''' numOfPermutation += P[n - i] ''// все перестановки с префиксом длиной i-1 равным нашему, и i-й элемент у которых <br />
''меньше нашего в лексикографическом порядке, идут раньше данной перестановки <br />
was[a[i]] = true ''// i-й элемент использован <br />
'''return''' numOfPermutation<br />
<br />
Данный алгоритм работает за <tex>O(n ^ 2) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*numOfBitvector {{---}} искомый номер вектора.<br />
*bitvector[1..n] {{---}} данный вектор.<br />
<br />
'''function''' bitvector2num(bitvector: '''list <int>''')<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
== Скобочные последовательности ==<br />
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8 Получение номера правильной скобочной последоватеьности]<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32mlhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=41781Получение номера по объекту2014-12-04T23:17:34Z<p>Dima32ml: /* Описание алгоритма */</p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму<br />
*<tex>numOfObject</tex> {{---}} искомый номер комбинаторного объекта.<br />
*<tex>a[1..n]</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.<br />
*<tex>d[i][j]</tex> - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)<br />
<br />
'''function''' object2num(a: '''list <A>''') <br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' ''// перебираем элементы комбинаторного объекта''<br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого'' <br />
'''if''' элемент j можно поставить на i-e место<br />
'''then''' numOfObject += d[i][j]<br />
'''return''' numOfObject<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.<br />
*P[1..n] {{---}} количество перестановок данного размера.<br />
*a[1..n] {{---}} данная перестановка.<br />
*was[1..n] {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
'''function''' permutation2num(a: '''list <int>''')<br />
numOfPermutation = 0<br />
'''for''' i = 1 '''to''' n '''do''' ''// n - количество элементов в перестановке''<br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элемент, лексикографически меньший нашего, который может стоять на i-м месте <br />
'''if''' was[j] == false ''// если элемент j ранее не был использован<br />
'''then''' numOfPermutation += P[n - i] ''// все перестановки с префиксом длиной i-1 равным нашему, и i-й элемент у которых <br />
''меньше нашего в лексикографическом порядке, идут раньше данной перестановки <br />
was[a[i]] = true ''// i-й элемент использован <br />
'''return''' numOfPermutation<br />
<br />
Данный алгоритм работает за <tex>O(n ^ 2) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.<br />
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*numOfBitvector {{---}} искомый номер вектора.<br />
*bitvector[1..n] {{---}} данный вектор.<br />
<br />
'''function''' bitvector2num(bitvector: '''list <int>''')<br />
numOfBitvector = 0<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 <br />
numOfBitvector += pow(2, n - i)<br />
'''return''' numOfBitvector<br />
<br />
== Скобочные последовательности ==<br />
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8 Получение номера правильной скобочной последоватеьности]<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>Dima32ml