Получение объекта по номеру — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 97 промежуточных версий 13 участников)
Строка 1: Строка 1:
== Общий алгоритм получения комбинаторного объекта по номеру в лексикографическом порядке ==
+
== Описание алгоритма ==
  ''//В начале каждого шага numOfObject -  номер комбинаторного объекта среди объектов с заданным префиксом. ''
+
Получаем элементы объекта по порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы нашли первые <tex>i</tex> элементов объекта. Для всех вариантов элемента, который может стоять на позиции с номером <tex>i+1</tex>, посчитаем диапазон номеров, который будет соответствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должен стоять на месте с номером <tex>i+1</tex>. Диапазоны номеров не пересекаются, значит на это место больше нельзя поставить никакой другой элемент:
  '''for'''  i = 1  '''to'''  n  '''do'''                      ''//n - количество элементов в комбинаторном объекте''
 
    '''for'''  j = 1 '''to'''  n  '''do'''                      ''//перебираем елементы в лексикографическом порядке''
 
      '''if'''  можем поставить на i-e место
 
        '''then if''' numOfObject > (количество комбинаторных обектов с данным префиксом)'''
 
              '''then'''  numOfObject -= (количество комбинаторных обектов с данным префиксом)
 
            '''else'''
 
              '''then'''  ans[i]=j        ''//поставим на i-e место текущий элемент, т.к. еще не все объекты с этим префиксом - меньше''
 
                    перейти к выбору следующего элемента
 
  
Рассмотрим почему данный алгоритм корректен. Докажем по индукции, что мы верно выберем первые i-элементов объекта.
+
*в начале каждого шага <tex>\mathtt{numOfObject}</tex> {{---}} номер нужного объекта среди тех, у которых префикс до <tex>i</tex>-го элемента лексикографически равен префиксу нашего объекта,
Условимся, что нумерация обектов начинается с 1.
+
*<tex>\mathtt{n}</tex> {{---}} количество мест в комбинаторном объекте (например, битовый вектор длины <tex>n</tex>),
: База: i=0 - очевидно
+
*<tex>\mathtt{k}</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2</tex>, поскольку возможны только <tex>0</tex> и <tex>1</tex>. Все элементы занумерованы в лексикографическом порядке, начиная с <tex>1</tex>.
: Докажем, что если первые i-элементов выбраны верно, то i+1 мы также выберем верно
+
Комбинаторные объекты занумерованы с <tex>0</tex>. Переход к нумерации с единицы можно сделать с помощью одной операции декремента перед проходом алгоритма:  
Переход: На i+1-ом шаге мы найдем, какой элемент должен быть i+1-ым для объекта с номером numOfOject, среди всех комбинаторных обектов, которые имеют префикс длины i - как у нас. <br> Рассмотрим искомый объект. Очевидно, что все объекты, у которых символ на
+
  '''function''' num2object(numOfObject: '''int'''):
i+1 месте меньше чем у нас в лексикографическом порядке, будут идти раньше нас (префикс совпадает, а i+1 символ меньше), т.е. наш номер, по крайней мере больше, количества таких объектов. А те у которых больше будут идти после нас, т.е. даже номер найменьшего из них будет больше нашего. Тогда <br>
+
  '''for''' i = 1 '''to''' n                   
(суммы всех комбинаторных объектов с ">=" префиксом) >= numOfObject > (суммы всех комбинаторных объектов с меньшим "<" префиксом) <br>  
+
    '''for''' j = 1 '''to''' k                     
т.е. в итоге из построения алгоритма мы поставим именно тот элемент, который нам нужен. <br> Далее продолжим искать среди объектов, которые имеют одинаковый префикс длины i+1, изменив номер на номер среди комбинаторных объектов с текущим префиксом. <br>
+
      '''if''' j-й элемент можно поставить на i-e место
Очевидно, это тоже самое, что искать старый номер, среди старых префиксов.
+
        '''if''' numOfObject >= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i)
 +
          numOfObject -= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i)
 +
        '''else'''
 +
          object[i] = j
 +
          break
 +
  '''return''' object
 +
Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью.
 +
Приведем примеры получения некоторых [[Комбинаторные объекты|комбинаторных объектов]] по номеру.
 +
 
 +
== Битовые вектора ==
 +
Рассмотрим алгоритм получения <tex>k</tex>-ого в лексикографическом порядке битового вектора размера <tex>n</tex>.
 +
При построении битовых векторов можно не проверять условие возможности постановки какого-то объекта на текущее место. На каждый позиции может стоять один из двух элементов, независимо от того, какие элементы находятся в префиксе. Так как у нас всего два возможных элемента, упростим второй цикл до условия:
 +
 
 +
*<tex>\mathtt{bitvector[n]}</tex> {{---}} искомый битовый вектор,
 +
*<tex>\mathtt{numOfBitvector}</tex> {{---}} номер искомого вектора среди всех битовых векторов,
 +
*<tex>\mathtt{pow(2, n)}</tex> {{---}} <tex>2^{n}</tex> количество битовых векторов длины <tex>n</tex>,
 +
'''vector<int>''' num2bitvector(numOfBitvector: '''int'''):
 +
  '''for''' i = 1 '''to''' n                                     
 +
    '''if''' numOfBitvector >= pow(2, (n - i))
 +
      numOfBitvector -= pow(2, (n - i))
 +
      bitvector[i] = 1
 +
    '''else'''
 +
      bitvector[i] = 0   
 +
  '''return''' bitvector   
 +
Данный алгоритм работает за <tex>O(n)</tex>, так как в случае битовых векторов <tex>k</tex> не зависит от <tex>n</tex>.
 +
Алгоритм эквивалентен переводу числа из десятичной системы в двоичную.
  
 
== Перестановки ==
 
== Перестановки ==
Рассмотрим алгоритм получения i-ой в лексикографическом порядке перестановки размера n.
+
Рассмотрим алгоритм получения <tex>k</tex>-ой в [[Лексикографический порядок|лексикографическом порядке]] перестановки размера <tex>n</tex>.
  <tex>P_{n} </tex> ''- количество перестановок размера n
+
Заметим, что всем префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество всевозможных суффиксов зависит только от длины) то есть можем просто посчитать "количество диапазонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>:
  permutation[n] ''- искомая перестановка''
+
 
  was[n] ''- использовали ли мы уже эту цифру в перестановке''
+
*<tex>\mathtt{k}</tex> {{---}} номер искомой последовательности,
  '''for'''  i = 1  '''to'''  n  '''do'''                              ''//n - количество цифр в перестановке''
+
*<tex>\mathtt{n!}</tex> {{---}} количество перестановок размера <tex>n</tex>,
    alreadyWas = (numOfPermutation-1) div <tex>P_{n-i} </tex>     ''// сколько цифр уже полностью заняты перестановками с меньшим номером''
+
*<tex>\mathtt{permutation[n]}</tex> {{---}} искомая перестановка,
    numOfPermutation = ((numOfPermutation-1) mod <tex>P_{n-i} </tex>) + 1
+
*<tex>\mathtt{was[n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке.
    ''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1, которая еще не занята''
+
На <tex>i</tex>-ом шаге:
    '''for''' j = 1 '''to''' n '''do'''
+
*<tex>\mathtt{alreadyWas}</tex> {{---}} сколько цифр уже полностью заняты перестановками с меньшим номером,
      '''if''' was[j] = false 
+
*мы должны поставить ту цифру, которая еще полностью не занята, то есть цифру с номером <tex>alreadyWas + 1</tex>. Среди цифр, которых еще нет в нашем префиксе, считаем, что это цифра <tex>j</tex>.
        '''then '''  cntFree++  
+
На <tex>j</tex>-ом шаге:
              '''if''' cntFree = alreadyWas+1
+
*<tex>\mathtt{curFree}</tex> {{---}} если элемент с номером <tex>j</tex> свободен, то он имеет номер curFree среди всех свободных элементов с <tex>1</tex> по <tex>j</tex>.
                '''then '''  ans[i] = j  
+
'''list<int>''' num2permutation(k: '''int'''):
                        was[j] = true
+
  '''for''' i = 1 '''to''' n                              
 +
    alreadyWas = k / (n - i)!     
 +
    k %= (n - i)!
 +
    curFree = 0
 +
    '''for''' j = 1 '''to'''
 +
      '''if''' was[j] == ''false''  
 +
        curFree++
 +
        '''if''' curFree == alreadyWas + 1
 +
          permutation[i] = j
 +
          was[j] = true
 +
  '''return''' permutation
  
Данный алгоритм работает за <tex>O(n^2) </tex>. Мы можем посчитать <tex>P_{n} </tex> за <tex>O(n) </tex>. Асимптотику можно улучшить  
+
Данный алгоритм работает за <tex>O(n^2)</tex>, так как в случае перестановок <tex>n=k</tex>. Мы можем посчитать все <tex>\mathtt{n!}</tex> за <tex>O(n) </tex>. Асимптотику можно улучшить  
до <tex>O(n log {n}) </tex>, если использовать структуры данных, которые позволяют искать i-ый элемент множества и удалять элемент  
+
до <tex>O(n \log {n}) </tex>, если использовать структуры данных (например, [[Декартово дерево|декартово дерево]] по неявному ключу), которые позволяют искать <tex>i</tex>-й элемент множества и удалять элемент  
множества за <tex>O( log {n}) </tex>. Например декартово дерево по неявному ключу.
+
множества за <tex>O( \log {n}) </tex>.
  
 
== Сочетания ==
 
== Сочетания ==
Рассмотрим алгоритм получения i-го в лексикографическом порядке размещения <tex> A^k_n </tex>
+
На каждой итерации мы проверяем, входит ли число <tex>\mathtt{next}</tex> в искомое сочетание. Если мы хотим взять <tex>\mathtt{next}</tex>, то номер сочетания должен быть меньше, чем <tex dpi=140>\binom{n - 1}{k - 1}</tex>, так как потом надо будет выбрать <tex>k - 1</tex> элемент из <tex>n - 1</tex> доступных. Если нет, то будем считать, что <tex dpi=140>\binom{n - 1}{k - 1}</tex> сочетаний, начинающихся с <tex>\mathtt{next}</tex>, мы пропустили. В обоих случаях рассмотрение текущего числа <tex>next</tex> мы заканчиваем и переходим к следующему числу.
  <tex>A^{k}_{n} </tex> ''- количество размещений из n по k
+
*<tex>\mathtt{choose}</tex> {{---}} искомое сочетание,
  placement[n] ''- искомое размещение''
+
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,
  was[n] ''- использовали ли мы уже эту цифру в размещении''
 
  '''for'''  i = 1 '''to'''  k  '''do'''                              ''//k - количество цифр в размещении''
 
    alreadyWas = (numOfPlacement-1) div <tex> A^{k-i}_{n-i} </tex>     ''// сколько цифр уже полностью заняты размещениями с меньшим номером''
 
    numOfPlacement = ((numOfPlacement-1) mod <tex> A^{k-i}_{n-i} </tex>) + 1
 
    ''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1, которая еще не занята''
 
    '''for'''  j = 1  '''to'''  n '''do'''
 
      '''if'''  was[j] = false 
 
        '''then '''  cntFree++
 
              '''if'''  cntFree = alreadyWas+1
 
                '''then '''  ans[i] = j
 
                        was[j] = true
 
Сложность алгоритма <tex>O(nk) </tex>.
 
  
== Размещения ==
+
'''list<int>''' num2choose(n, k, m: '''int'''):
== Битовые вектора ==
+
  next = 1
== Скобочные последовательности ==
+
  '''while''' k > 0
== Разложение на слагаемые ==
+
    '''if''' m < C[n - 1][k - 1]
 +
      choose.push_back(next)
 +
      k = k - 1
 +
    '''else'''
 +
      m -= C[n - 1][k - 1]
 +
    n = n - 1
 +
    next = next + 1
 +
  '''return''' choose
 +
Асимптотика приведенного алгоритма {{---}} <tex>O(n)</tex>, предподсчет <tex>\mathtt{C[n][k]}</tex>  {{---}} <tex>O(n^2)</tex>
 +
 
 +
== См. также ==
 +
*[[Получение номера по объекту|Получение номера по объекту]]
 +
*[[Получение_предыдущего_объекта#.D0.A1.D0.BF.D0.B5.D1.86.D0.B8.D0.B0.D0.BB.D0.B8.D0.B7.D0.B0.D1.86.D0.B8.D1.8F_.D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D0.B0_.D0.B4.D0.BB.D1.8F_.D0.B3.D0.B5.D0.BD.D0.B5.D1.80.D0.B0.D1.86.D0.B8.D0.B8_.D0.BF.D1.80.D0.B5.D0.B4.D1.8B.D0.B4.D1.83.D1.89.D0.B5.D0.B3.D0.BE_.D1.81.D0.BE.D1.87.D0.B5.D1.82.D0.B0.D0.BD.D0.B8.D1.8F|Получение предыдущего сочетания]]
 +
*[[Получение_следующего_объекта#.D0.A1.D0.BF.D0.B5.D1.86.D0.B8.D0.B0.D0.BB.D0.B8.D0.B7.D0.B0.D1.86.D0.B8.D1.8F_.D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D0.B0_.D0.B4.D0.BB.D1.8F_.D0.B3.D0.B5.D0.BD.D0.B5.D1.80.D0.B0.D1.86.D0.B8.D0.B8_.D1.81.D0.BB.D0.B5.D0.B4.D1.83.D1.8E.D1.89.D0.B5.D0.B3.D0.BE_.D1.81.D0.BE.D1.87.D0.B5.D1.82.D0.B0.D0.BD.D0.B8.D1.8F|Генерация следующего сочетания]]
 +
== Источники информации ==
 +
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31 - ISBN 5-94774-010-9
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Комбинаторика]]

Текущая версия на 19:30, 4 сентября 2022

Описание алгоритма

Получаем элементы объекта по порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы нашли первые [math]i[/math] элементов объекта. Для всех вариантов элемента, который может стоять на позиции с номером [math]i+1[/math], посчитаем диапазон номеров, который будет соответствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должен стоять на месте с номером [math]i+1[/math]. Диапазоны номеров не пересекаются, значит на это место больше нельзя поставить никакой другой элемент:

  • в начале каждого шага [math]\mathtt{numOfObject}[/math] — номер нужного объекта среди тех, у которых префикс до [math]i[/math]-го элемента лексикографически равен префиксу нашего объекта,
  • [math]\mathtt{n}[/math] — количество мест в комбинаторном объекте (например, битовый вектор длины [math]n[/math]),
  • [math]\mathtt{k}[/math] — количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора [math]k=2[/math], поскольку возможны только [math]0[/math] и [math]1[/math]. Все элементы занумерованы в лексикографическом порядке, начиная с [math]1[/math].

Комбинаторные объекты занумерованы с [math]0[/math]. Переход к нумерации с единицы можно сделать с помощью одной операции декремента перед проходом алгоритма:

function num2object(numOfObject: int):
  for i = 1 to n                     
    for j = 1 to k                      
      if j-й элемент можно поставить на i-e место 
        if numOfObject >= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i)
          numOfObject -= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i)
        else
          object[i] = j
          break
  return object

Сложность алгоритма — [math]O(nk) [/math]. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью. Приведем примеры получения некоторых комбинаторных объектов по номеру.

Битовые вектора

Рассмотрим алгоритм получения [math]k[/math]-ого в лексикографическом порядке битового вектора размера [math]n[/math]. При построении битовых векторов можно не проверять условие возможности постановки какого-то объекта на текущее место. На каждый позиции может стоять один из двух элементов, независимо от того, какие элементы находятся в префиксе. Так как у нас всего два возможных элемента, упростим второй цикл до условия:

  • [math]\mathtt{bitvector[n]}[/math] — искомый битовый вектор,
  • [math]\mathtt{numOfBitvector}[/math] — номер искомого вектора среди всех битовых векторов,
  • [math]\mathtt{pow(2, n)}[/math][math]2^{n}[/math] количество битовых векторов длины [math]n[/math],
vector<int> num2bitvector(numOfBitvector: int):
  for i = 1 to n                                      
   if numOfBitvector >= pow(2, (n - i))
     numOfBitvector -= pow(2, (n - i))
     bitvector[i] = 1
   else
     bitvector[i] = 0    
  return bitvector    

Данный алгоритм работает за [math]O(n)[/math], так как в случае битовых векторов [math]k[/math] не зависит от [math]n[/math]. Алгоритм эквивалентен переводу числа из десятичной системы в двоичную.

Перестановки

Рассмотрим алгоритм получения [math]k[/math]-ой в лексикографическом порядке перестановки размера [math]n[/math]. Заметим, что всем префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество всевозможных суффиксов зависит только от длины) то есть можем просто посчитать "количество диапазонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за [math]O(1) [/math]:

  • [math]\mathtt{k}[/math] — номер искомой последовательности,
  • [math]\mathtt{n!}[/math] — количество перестановок размера [math]n[/math],
  • [math]\mathtt{permutation[n]}[/math] — искомая перестановка,
  • [math]\mathtt{was[n]}[/math] — использовали ли мы уже эту цифру в перестановке.

На [math]i[/math]-ом шаге:

  • [math]\mathtt{alreadyWas}[/math] — сколько цифр уже полностью заняты перестановками с меньшим номером,
  • мы должны поставить ту цифру, которая еще полностью не занята, то есть цифру с номером [math]alreadyWas + 1[/math]. Среди цифр, которых еще нет в нашем префиксе, считаем, что это цифра [math]j[/math].

На [math]j[/math]-ом шаге:

  • [math]\mathtt{curFree}[/math] — если элемент с номером [math]j[/math] свободен, то он имеет номер curFree среди всех свободных элементов с [math]1[/math] по [math]j[/math].
list<int> num2permutation(k: int):
  for i = 1 to n                               
    alreadyWas = k / (n - i)!      
    k %= (n - i)!
    curFree = 0
    for j = 1 to n  
      if was[j] == false 
        curFree++
        if curFree == alreadyWas + 1
          permutation[i] = j
          was[j] = true
  return permutation

Данный алгоритм работает за [math]O(n^2)[/math], так как в случае перестановок [math]n=k[/math]. Мы можем посчитать все [math]\mathtt{n!}[/math] за [math]O(n) [/math]. Асимптотику можно улучшить до [math]O(n \log {n}) [/math], если использовать структуры данных (например, декартово дерево по неявному ключу), которые позволяют искать [math]i[/math]-й элемент множества и удалять элемент множества за [math]O( \log {n}) [/math].

Сочетания

На каждой итерации мы проверяем, входит ли число [math]\mathtt{next}[/math] в искомое сочетание. Если мы хотим взять [math]\mathtt{next}[/math], то номер сочетания должен быть меньше, чем [math]\binom{n - 1}{k - 1}[/math], так как потом надо будет выбрать [math]k - 1[/math] элемент из [math]n - 1[/math] доступных. Если нет, то будем считать, что [math]\binom{n - 1}{k - 1}[/math] сочетаний, начинающихся с [math]\mathtt{next}[/math], мы пропустили. В обоих случаях рассмотрение текущего числа [math]next[/math] мы заканчиваем и переходим к следующему числу.

  • [math]\mathtt{choose}[/math] — искомое сочетание,
  • [math]\mathtt{C[n][k]}[/math] — количество сочетаний из [math]n[/math] по [math]k[/math], [math]\mathtt{C[n][0] = 1}[/math],
list<int> num2choose(n, k, m: int):
  next = 1
  while k > 0
    if m < C[n - 1][k - 1]
      choose.push_back(next)
      k = k - 1
    else
      m -= C[n - 1][k - 1]
    n = n - 1
    next = next + 1
  return choose

Асимптотика приведенного алгоритма — [math]O(n)[/math], предподсчет [math]\mathtt{C[n][k]}[/math][math]O(n^2)[/math]

См. также

Источники информации

  • Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31 - ISBN 5-94774-010-9