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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
Строка 2: Строка 2:
 
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с 0). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>).  
 
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с 0). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>).  
 
Следующий алгоритм вычисляет эту сумму
 
Следующий алгоритм вычисляет эту сумму
*'''numOfObject''' {{---}} искомый номер комбинаторного объекта.
+
*numOfObject''' {{---}} искомый номер комбинаторного объекта.
*'''a[1..n]''' {{---}} данный комбинаторный обьект.
+
*a[1..n] {{---}} данный комбинаторный обьект.
*'''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                           
 
   numOfObject = 0                           
 
   '''for''' i = 1 '''to''' n '''do'''                        ''// перебираем элементы комбинаторного объекта''
 
   '''for''' i = 1 '''to''' n '''do'''                        ''// перебираем элементы комбинаторного объекта''

Версия 07:42, 24 декабря 2011

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

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

  • numOfObject — искомый номер комбинаторного объекта.
  • a[1..n] — данный комбинаторный обьект.
  • d[i][j] - (количество комбинаторных объектов с префиксом от 1 до [math]i-1[/math] равным данному и с [math]i[/math]-м элементом равным [math]j[/math])
 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]

Сложность алгоритма — [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] — использовали ли мы уже эту цифру в перестановке.
 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[i] = true                       // элемент i использован            

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

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

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

  • numOfBitvector — искомый номер вектора.
  • bitvector[1..n] — данный вектор.
for i = 1 to n do                                         
 if bitvector[i] == 1  {
    numOfBitvector += 2 ^ (n - i)        
 }

См. также

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