Редактирование: Получение номера по объекту

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
== Описание алгоритма ==
 
== Описание алгоритма ==
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>(i+1)</tex>-го в данном объекте (<tex>i = 0..n-1</tex>).  
+
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>).  
 
Следующий алгоритм вычисляет эту сумму:
 
Следующий алгоритм вычисляет эту сумму:
 
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,
 
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из числовых представлений лексикографически упорядоченных элементов множества <tex>A</tex>,
+
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>,
 
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,
 
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,
  
 
  '''int''' object2num(a: '''list<A>'''):
 
  '''int''' object2num(a: '''list<A>'''):
 
   numOfObject = 0                           
 
   numOfObject = 0                           
   '''for''' i = 1 '''to''' n                   <font color=green>// перебираем элементы комбинаторного объекта</font>
+
   '''for''' i = 1 '''to''' n '''do'''                        <font color=green>// перебираем элементы комбинаторного объекта</font>
     '''for''' j = 1 '''to''' a[i] - 1          <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font>
+
     '''for''' j = <tex>A_{min}</tex> '''to''' предшествующий элемент '''do'''              <font color=green>// перебираем элементы, которые в лексикографическом порядке меньше  рассматриваемого</font>
 
       '''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место
 
       '''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место
 
         numOfObject += d[i][j]
 
         numOfObject += d[i][j]
 
   '''return''' numOfObject
 
   '''return''' numOfObject
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.  
+
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {---} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.  
 
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.
 
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.
  
Строка 19: Строка 19:
 
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.
 
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.
 
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.
 
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск элементов меньше рассматриваемого можно упростить до проверки элемента на равенство <tex>1</tex>:  
+
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия:  
 
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,
 
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,
 
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,
 
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,
Строка 25: Строка 25:
 
  '''int''' bitvector2num(bitvector: '''list<int>'''):
 
  '''int''' bitvector2num(bitvector: '''list<int>'''):
 
   numOfBitvector = 0
 
   numOfBitvector = 0
   '''for''' i = 1 '''to''' n                                      
+
   '''for''' i = 1 '''to''' n '''do'''                                       
 
     '''if''' bitvector[i] == 1   
 
     '''if''' bitvector[i] == 1   
       numOfBitvector += <tex>2^{n-i}</tex>
+
       numOfBitvector += pow(2, n - i)
 
   '''return''' numOfBitvector
 
   '''return''' numOfBitvector
  
Строка 40: Строка 40:
 
  '''int''' permutation2num(a: '''list<int>'''):
 
  '''int''' permutation2num(a: '''list<int>'''):
 
   numOfPermutation = 0
 
   numOfPermutation = 0
   '''for''' i = 1 '''to''' n                       <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font>  
+
   '''for''' i = 1 '''to''' n '''do'''                    <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font>  
     '''for''' j = 1  '''to''' a[i] - 1             <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font>   
+
     '''for''' j = 1  '''to''' a[i] - 1 '''do'''          <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font>   
 
       '''if''' was[j] == ''false''                <font color=green>// если элемент <tex>j</tex> ранее не был использован</font>  
 
       '''if''' was[j] == ''false''                <font color=green>// если элемент <tex>j</tex> ранее не был использован</font>  
 
         numOfPermutation += P[n - i]    <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font>   
 
         numOfPermutation += P[n - i]    <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font>   
Строка 48: Строка 48:
 
   '''return''' numOfPermutation
 
   '''return''' numOfPermutation
  
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex> и <tex>O(n) </tex> для предподсчёта.
+
Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </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>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>. Аналогично продолжаем по следующим позициям:
 
*<tex>\mathtt{numOfChoose}</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{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>,
 
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,
  
 +
<font color=green>// Нумерация сочетаний с <tex>0</tex></font>
 
  '''int''' choose2num(choose: '''list<int>'''):
 
  '''int''' choose2num(choose: '''list<int>'''):
 
   numOfChoose = 0
 
   numOfChoose = 0
   '''for''' i = 1 '''to''' K                                      
+
   '''for''' i = 1 '''to''' K '''do'''                                       
     '''for'''  j = choose[i - 1] + 1 '''to''' choose[i] - 1
+
     '''for'''  i = choose[i - 1] + 1 '''to''' choose[i] - 1 '''do'''
 
       numOfChoose += C[N - j][K - i]
 
       numOfChoose += C[N - j][K - i]
 
   '''return''' numOfChoose
 
   '''return''' numOfChoose
  
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex> и <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|Получение номера правильной скобочной последовательности]]
 
*[[Правильные скобочные последовательности#.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
 
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31
 
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.
 
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: