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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 159 промежуточных версий 17 участников)
Строка 1: Строка 1:
== Общий алгоритм получения номера в лексикографическом порядке по комбинаторному объекту ==
+
== Описание алгоритма ==
Номер данного комбинаторного объекта равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов плюс 1(нумерацию ведём с 1).Все объекты меньшие нашего можно разбить на непересекающиеся группы по длине совпадающего префикса.Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины i совпадает , а i+1 элемент лексикографически меньше i+1-го в данном объекте(i=0..n-1).  
+
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>(i+1)</tex>-го в данном объекте (<tex>i = 0..n-1</tex>).  
Следующий алгоритм вычисляет эту сумму
+
Следующий алгоритм вычисляет эту сумму:
  numOfObject=1                              ''// numOfObject {{---}} искомый номер комбинаторного объекта
+
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,
  '''for''' i = 1  '''to''' '''do'''                     ''//перебираем элементы комбинаторного объекта''
+
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из числовых представлений лексикографически упорядоченных элементов множества <tex>A</tex>,
    '''for''' j = 1 '''to''' i-1 '''do'''                      ''//перебираем элементы которые в лексикографическом порядке меньше рассматриваемого''
+
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,
      '''if''' элемент j можно поставить на i-e место
+
 
        '''then numOfObject+=(коллличество комбинаторных объектов с данным префиксом)
+
'''int''' object2num(a: '''list<A>'''):
т.е. он правильно находит номер данного объекта.
+
  numOfObject = 0                         
   
+
  '''for''' i = 1 '''to''' n                  <font color=green>// перебираем элементы комбинаторного объекта</font>
Несложно понять, что корректность алгоритма следует из его построения.
+
    '''for''' j = 1 '''to''' a[i] - 1         <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font>
Сложность алгоритма <tex>O(n^{2}f(1..i)) </tex>, где <tex>f(1..i)</tex> - сложность вычисления количества комбинаторных объектов с данным префиксом. Основную сложность при построении алгоритмов генерации комбинаторных объектов составляет вычисление количества комбинаторных объектов с данным префиксом. Приведем примеры способов нахождения количества некоторых из [[Комбинаторные объекты|комбинаторных объектов]].  
+
      '''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место
 +
        numOfObject += d[i][j]
 +
  '''return''' numOfObject
 +
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.  
 +
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.
 +
 
 +
== Битовые вектора ==
 +
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.
 +
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.
 +
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск элементов меньше рассматриваемого можно упростить до проверки элемента на равенство <tex>1</tex>:
 +
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,
 +
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,
 +
 
 +
'''int''' bitvector2num(bitvector: '''list<int>'''):
 +
  numOfBitvector = 0
 +
  '''for''' i = 1 '''to''' n                                       
 +
    '''if''' bitvector[i] == 1 
 +
      numOfBitvector += <tex>2^{n-i}</tex>
 +
  '''return''' numOfBitvector
 +
 
 +
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.
  
 
== Перестановки ==
 
== Перестановки ==
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановки размера n.
+
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,
  <tex>P_{n} </tex> ''{{---}} количество перестановок размера n
+
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,
  permutation[n] ''{{---}} данная перестановка''
+
*<tex>\mathtt{(n - i)!}</tex> {{---}} количество перестановок размера <tex>(n - i)</tex>,
  was[n] ''{{---}} использовали ли мы уже эту цифру в перестановке''
+
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,
  '''for''' i = 1  '''to''' '''do'''                               ''//n - количество цифр в перестановке''
+
 
    '''for''' j = 1  '''to''' a[i]-1 '''do'''                          ''//перебираем символ который может стоять на i-м месте лексикографически меньше нашего
+
'''int''' permutation2num(a: '''list<int>'''):
      '''if''' was[j] = false
+
  numOfPermutation = 0
        '''then ''' numOfPermutation += <tex>P_{n-i} </tex>  
+
  '''for''' i = 1 '''to''' n                        <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font>
 +
    '''for''' j = 1  '''to''' a[i] - 1             <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> 
 +
      '''if''' was[j] == ''false''               <font color=green>// если элемент <tex>j</tex> ранее не был использован</font>
 +
        numOfPermutation += (n - i)!    <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> 
 +
                                            <font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font>               
 +
    was[a[i]] = ''true''                   <font color=green>// <tex>i</tex>-й элемент использован</font>           
 +
  '''return''' numOfPermutation
  
Данный алгоритм работает за <tex>O(n^2) </tex>. Мы можем посчитать <tex>P_{n} </tex> за <tex>O(n) </tex>. Асимптотику можно улучшить
+
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex> и <tex>O(n) </tex> для предподсчёта.
до <tex>O(n log {n}) </tex>, если использовать структуры данных, которые позволяют искать i-ый элемент множества и удалять элемент
 
множества за <tex>O( log {n}) </tex>. Например декартово дерево по неявному ключу.
 
  
 +
== Сочетания ==
 +
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <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>. Аналогично продолжаем по следующим позициям:
 +
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,
 +
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,
 +
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,
  
== Битовые вектора ==
+
'''int''' choose2num(choose: '''list<int>'''):
 +
  numOfChoose = 0
 +
  '''for''' i = 1 '''to''' K                                     
 +
    '''for'''  j = choose[i - 1] + 1 '''to''' choose[i] - 1
 +
      numOfChoose += C[N - j][K - i]
 +
  '''return''' numOfChoose
 +
 
 +
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex> и <tex>O(K \cdot N) </tex> для предподсчёта.
 +
 
 +
== Разбиение на слагаемые ==
 +
Рассмотрим алгоритм получения номера, в лексикографическом порядке, по данному разбиению на слагаемые числа <tex>N</tex>. Нужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Из всех разбиений, получаемых перестановками слагаемых, выберем то, где слагаемые упорядочены лексикографически, и будем строить его. 
 +
 
 +
*<tex>\mathtt{numOfPart}</tex> {{---}} искомый номер разбиения
 +
*<tex>\mathtt{last}</tex> {{---}} последнее поставленное число в разбиении.
 +
*<tex>\mathtt{sum}</tex> {{---}} сумма, которую мы уже поставили.
 +
*<tex>\mathtt{part[1 \ldots N]}</tex> {{---}} данное разбиение
 +
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество разбиений числа <tex>i</tex> на слагаемые, где каждое слагаемое <tex>\geqslant j</tex>. 
 +
 
 +
Пересчитывать <tex>\mathtt{d[i][j]}</tex> будем по возрастанию <tex>i</tex>, а при равенстве <tex>i</tex> {{---}} по убыванию <tex>j</tex>.
 +
 
 +
Разбиение числа, в котором каждое слагаемое <tex> \geqslant j</tex> может либо содержать слагаемое <tex>j</tex> (таких разбиений <tex>\mathtt{d[i - j][j]}</tex>), либо не содержать (таких разбиений <tex>\mathtt{d[i][j + 1]}</tex>).
 +
 
 +
Получаем рекуррентное соотношение для подсчёта <tex>d</tex>:
 +
 
 +
<p>
 +
<tex dpi = "145">d[i][j] =
 +
\left \{\begin{array}{ll} 1, & i = j, \\ 0, & i < j  \\ d[i][j + 1] + d[i - j][j], & i > j \end{array} \right.
 +
</tex>
 +
</p>
 +
 
 +
 
 +
'''int''' part2num(part: '''list<int>'''):
 +
  numOfPart = 0, last = 0, sum = 0
 +
  '''for''' i = 1 '''to''' part.size
 +
    '''for''' j = last '''to''' part[i] - 1            <font color=green>// перебираем все элементы, лексикографически меньшие текущего, но не меньшие предыдущего</font>   
 +
      numOfPart += d[N - sum - j][j]      <font color=green>// прибавляем количество перестановок, которые могли начинаться с <tex>j</tex></font>
 +
    sum += part[i]                        <font color=green>// увеличиваем уже поставленную сумму</font>
 +
    last = part[i]                        <font color=green>// обновляем последний поставленный элемент </font>
 +
  '''return''' numOfPart                        <font color=green>// возвращаем ответ</font>
 +
 
 +
Стоит отметить, что количество итераций вложенного цикла не более, чем <tex>N</tex>, так как всего количество возможных слагаемых {{---}} <tex>N</tex>, и ни какое из них цикл не обработает дважды, поскольку каждый раз начинает с <tex>last</tex>, которое больше чем любое из обработанных чисел. Поэтому асимптотика алгоритма {{---}} <tex>O(N)</tex>.
 +
 
 +
Асимптотика алгоритма {{---}} <tex> O (N)</tex> и <tex>O(N^2)</tex> на предподсчёт.
  
 
== См. также ==
 
== См. также ==
[[Получение объекта по номеру|Получение объекта по номеру]]
+
*[[Получение объекта по номеру|Получение объекта по номеру]]
 +
*[[Получение следующего объекта|Получение следующего объекта]]
 +
*[[Правильные скобочные последовательности#.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|Получение номера правильной скобочной последовательности]]
 +
 
 +
== Источники информации ==
 +
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31
 +
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]

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

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

Номер данного комбинаторного объекта равен количеству меньших в лексикографическом порядке комбинаторных объектов (нумерацию ведём с [math]0[/math]). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины [math]i[/math] совпадает, а [math]i+1[/math] элемент лексикографически меньше [math](i+1)[/math]-го в данном объекте ([math]i = 0..n-1[/math]). Следующий алгоритм вычисляет эту сумму:

  • [math]\mathtt{numOfObject}[/math] — искомый номер комбинаторного объекта,
  • [math]\mathtt{a[1..n]}[/math] — данный комбинаторный обьект, состоящий из числовых представлений лексикографически упорядоченных элементов множества [math]A[/math],
  • [math]\mathtt{d[i][j]}[/math] — количество комбинаторных объектов с префиксом от [math]1[/math] до [math]i-1[/math] равным данному и с [math]i[/math]-м элементом равным [math]j[/math],
int object2num(a: list<A>):
  numOfObject = 0                          
  for i = 1 to n                   // перебираем элементы комбинаторного объекта
    for j = 1 to a[i] - 1          // перебираем элементы, в лексикографическом порядке меньшие рассматриваемого
      if элемент [math]j[/math] можно поставить на [math]i[/math]-e место
        numOfObject += d[i][j]
  return numOfObject

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

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

Рассмотрим алгоритм получения номера [math]i[/math] в лексикографическом порядке данного битового вектора размера [math]n[/math]. Всего существует [math]2^n[/math] битовых векторов длины [math]n[/math]. На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск элементов меньше рассматриваемого можно упростить до проверки элемента на равенство [math]1[/math]:

  • [math]\mathtt{bitvector[1..n]}[/math] — данный вектор,
  • [math]\mathtt{numOfBitvector}[/math] — искомый номер вектора,
int bitvector2num(bitvector: list<int>):
  numOfBitvector = 0
  for i = 1 to n                                        
    if bitvector[i] == 1  
      numOfBitvector += [math]2^{n-i}[/math]
  return numOfBitvector

Асимптотика алгоритма — [math]O(n) [/math].

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

Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера [math]n[/math],

  • [math]\mathtt{a[1..n]}[/math] — данная перестановка,
  • [math]\mathtt{(n - i)!}[/math] — количество перестановок размера [math](n - i)[/math],
  • [math]\mathtt{was[1..n]}[/math] — использовали ли мы уже эту цифру в перестановке,
int permutation2num(a: list<int>):
  numOfPermutation = 0
  for i = 1 to n                        // [math]n[/math] — количество элементов в перестановке 
    for j = 1  to a[i] - 1              // перебираем элементы, лексикографически меньшие нашего, которые могут стоять на [math]i[/math]-м месте  
      if was[j] == false                // если элемент [math]j[/math] ранее не был использован 
        numOfPermutation += (n - i)!    // все перестановки с префиксом длиной [math]i-1[/math] равным нашему, и [math]i[/math]-й элемент у которых   
                                           меньше нашего в лексикографическом порядке, идут раньше данной перестановки                
    was[a[i]] = true                    // [math]i[/math]-й элемент использован            
  return numOfPermutation

Асимптотика алгоритма — [math]O(n ^ 2) [/math] и [math]O(n) [/math] для предподсчёта.

Сочетания

Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из [math]n[/math] по [math]k[/math]. Как известно, количество сочетаний из [math]n[/math] по [math]k[/math] обозначается как [math]\binom{n}{k}[/math]. Тогда число сочетаний, в которых на позиции [math]1[/math] стоит значение [math]val_1[/math], равно [math]\sum\limits^{val_1-1}_{i=1} {\binom{n-i}{k-1}}[/math]; число сочетаний, в которых на позиции [math]2[/math] стоит значение [math]val_2[/math], равно [math]\sum\limits^{val_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}[/math]. Аналогично продолжаем по следующим позициям:

  • [math]\mathtt{numOfChoose}[/math] — искомый номер сочетания,
  • [math]\mathtt{C[n][k]}[/math] — количество сочетаний из [math]n[/math] по [math]k[/math], [math]\mathtt{C[n][0] = 1}[/math],
  • [math]\mathtt{choose[1..K]}[/math] — данное сочетание, состоящее из [math]K[/math] чисел от [math]1[/math] до [math]N[/math], из технических соображений припишем ноль в начало сочетания: [math]\mathtt{choose[0] = 0}[/math],
int choose2num(choose: list<int>):
  numOfChoose = 0
  for i = 1 to K                                       
    for  j = choose[i - 1] + 1 to choose[i] - 1
      numOfChoose += C[N - j][K - i]
  return numOfChoose

Асимптотика алгоритма — [math]O(K \cdot N) [/math] и [math]O(K \cdot N) [/math] для предподсчёта.

Разбиение на слагаемые

Рассмотрим алгоритм получения номера, в лексикографическом порядке, по данному разбиению на слагаемые числа [math]N[/math]. Нужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Из всех разбиений, получаемых перестановками слагаемых, выберем то, где слагаемые упорядочены лексикографически, и будем строить его.

  • [math]\mathtt{numOfPart}[/math] — искомый номер разбиения
  • [math]\mathtt{last}[/math] — последнее поставленное число в разбиении.
  • [math]\mathtt{sum}[/math] — сумма, которую мы уже поставили.
  • [math]\mathtt{part[1 \ldots N]}[/math] — данное разбиение
  • [math]\mathtt{d[i][j]}[/math] — количество разбиений числа [math]i[/math] на слагаемые, где каждое слагаемое [math]\geqslant j[/math].

Пересчитывать [math]\mathtt{d[i][j]}[/math] будем по возрастанию [math]i[/math], а при равенстве [math]i[/math] — по убыванию [math]j[/math].

Разбиение числа, в котором каждое слагаемое [math] \geqslant j[/math] может либо содержать слагаемое [math]j[/math] (таких разбиений [math]\mathtt{d[i - j][j]}[/math]), либо не содержать (таких разбиений [math]\mathtt{d[i][j + 1]}[/math]).

Получаем рекуррентное соотношение для подсчёта [math]d[/math]:

[math]d[i][j] = \left \{\begin{array}{ll} 1, & i = j, \\ 0, & i \lt j \\ d[i][j + 1] + d[i - j][j], & i \gt j \end{array} \right. [/math]


int part2num(part: list<int>):
  numOfPart = 0, last = 0, sum = 0
  for i = 1 to part.size
    for j = last to part[i] - 1            // перебираем все элементы, лексикографически меньшие текущего, но не меньшие предыдущего    
      numOfPart += d[N - sum - j][j]       // прибавляем количество перестановок, которые могли начинаться с [math]j[/math]
    sum += part[i]                         // увеличиваем уже поставленную сумму
    last = part[i]                         // обновляем последний поставленный элемент 
  return numOfPart                         // возвращаем ответ

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

Асимптотика алгоритма — [math] O (N)[/math] и [math]O(N^2)[/math] на предподсчёт.

См. также

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

  • Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31
  • Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.