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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
(Перестановки)
Строка 24: Строка 24:
 
  '''function''' permutation2num(a: '''list <int>''')
 
  '''function''' permutation2num(a: '''list <int>''')
 
   numOfPermutation = 0
 
   numOfPermutation = 0
   '''for''' i = 1 '''to''' n '''do'''                       ''// n - количество элементов в перестановке''
+
   '''for''' i = 1 '''to''' n '''do'''                     <font color=green>// <tex>n</tex> - количество элементов в перестановке</font>
     '''for''' j = 1  '''to''' a[i] - 1 '''do'''             ''// перебираем элемент, лексикографически меньший нашего, который может стоять на i-м месте  
+
     '''for''' j = 1  '''to''' a[i] - 1 '''do'''           <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> 
       '''if''' was[j] == false                   ''// если элемент j ранее не был использован
+
       '''if''' was[j] == false               <font color=green>// если элемент <tex>j</tex> ранее не был использован</font>
         '''then''' numOfPermutation += P[n - i]   ''// все перестановки с префиксом длиной i-1 равным нашему, и i-й элемент у которых
+
         numOfPermutation += P[n - i]   <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> 
                                              ''меньше нашего в лексикографическом порядке, идут раньше данной перестановки              
+
                                            <font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font>               
     was[a[i]] = true                       ''// i-й элемент использован             
+
     was[a[i]] = true                   <font color=green>// <tex>i</tex>-й элемент использован</font>            
 
   '''return''' numOfPermutation
 
   '''return''' numOfPermutation
  

Версия 03:03, 5 декабря 2014

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

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

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

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

Данный алгоритм работает за [math]O(n ^ 2) [/math].

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

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

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

Данный алгоритм работает за [math]O(n) [/math].

Скобочные последовательности

См. также

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