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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
Следующий алгоритм вычисляет эту сумму
 
Следующий алгоритм вычисляет эту сумму
 
*numOfObject {{---}} искомый номер комбинаторного объекта.
 
*numOfObject {{---}} искомый номер комбинаторного объекта.
*a[1..n] {{---}} данный комбинаторный обьект.
+
*a[1..n] {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.
 
*d[i][j] - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)
 
*d[i][j] - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)
  numOfObject = 0                           
+
 
  '''for''' i = 1 '''to''' n '''do'''                        ''// перебираем элементы комбинаторного объекта''
+
'''function''' NumOfObjectsFunc(a: '''list <A>''')
    '''for''' j = 1 '''to''' a[i] - 1 '''do'''              ''// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого''
+
  numOfObject = 0                           
      '''if''' элемент j можно поставить на i-e место
+
  '''for''' i = 1 '''to''' n '''do'''                        ''// перебираем элементы комбинаторного объекта''
        '''then''' numOfObject += d[i][j]
+
    '''for''' j = 1 '''to''' a[i] - 1 '''do'''              ''// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого''  
 +
      '''if''' элемент j можно поставить на i-e место
 +
        '''then''' numOfObject += d[i][j]
 +
  '''return''' numOfObject
 
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Для битового вектора <tex>k=2</tex>: возможны только 0 и 1. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.  
 
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Для битового вектора <tex>k=2</tex>: возможны только 0 и 1. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.  
 
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.
 
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.
Строка 19: Строка 22:
 
*was[1..n] {{---}} использовали ли мы уже эту цифру в перестановке.
 
*was[1..n] {{---}} использовали ли мы уже эту цифру в перестановке.
  
  '''for''' i = 1 '''to''' n '''do'''                      ''// n - количество элементов в перестановке''
+
'''function''' NumOfPermutationFunc(a: '''list <A>''')
    '''for''' j = 1  '''to''' a[i] - 1 '''do'''            ''// перебираем элемент, лексикографически меньший нашего, который может стоять на i-м месте  
+
  '''for''' i = 1 '''to''' n '''do'''                      ''// n - количество элементов в перестановке''
      '''if''' was[j] == false                    ''// если элемент j ранее не был использован
+
    '''for''' j = 1  '''to''' a[i] - 1 '''do'''            ''// перебираем элемент, лексикографически меньший нашего, который может стоять на i-м месте  
        '''then''' numOfPermutation += P[n - i]  ''// все перестановки с префиксом длиной i-1 равным нашему, и i-й элемент у которых   
+
      '''if''' was[j] == false                    ''// если элемент j ранее не был использован
 +
        '''then''' numOfPermutation += P[n - i]  ''// все перестановки с префиксом длиной i-1 равным нашему, и i-й элемент у которых   
 
                                               ''меньше нашего в лексикографическом порядке, идут раньше данной перестановки               
 
                                               ''меньше нашего в лексикографическом порядке, идут раньше данной перестановки               
    was[a[i]] = true                      ''// i-й элемент использован             
+
    was[a[i]] = true                      ''// i-й элемент использован             
 +
  '''return''' numOfPermutation
  
 
Данный алгоритм работает за <tex>O(n ^ 2) </tex>.
 
Данный алгоритм работает за <tex>O(n ^ 2) </tex>.
Строка 34: Строка 39:
 
*numOfBitvector {{---}} искомый номер вектора.
 
*numOfBitvector {{---}} искомый номер вектора.
 
*bitvector[1..n] {{---}} данный вектор.
 
*bitvector[1..n] {{---}} данный вектор.
  '''for''' i = 1 '''to''' n '''do'''                                         
+
 
  '''if''' bitvector[i] == 1   
+
  '''function''' NumOfBitvectorFunc(bitvector: '''Binary''')
    numOfBitvector += 2 ** (n - i)
+
  '''for''' i = 1 '''to''' n '''do'''                                         
 +
    '''if''' bitvector[i] == 1   
 +
        numOfBitvector += 2 ** (n - i)
 +
  '''return''' numOfBitvector 
  
 
== См. также ==
 
== См. также ==

Версия 16:36, 12 декабря 2013

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

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

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

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

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

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

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

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

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

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

  • numOfBitvector — искомый номер вектора.
  • bitvector[1..n] — данный вектор.
function NumOfBitvectorFunc(bitvector: Binary)
  for i = 1 to n do                                         
   if bitvector[i] == 1  
        numOfBitvector += 2 ** (n - i)
  return numOfBitvector  

См. также

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