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

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

Версия 06:19, 26 ноября 2011

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

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

 numOfObject = 0                              // numOfObject — искомый номер комбинаторного объекта
 for  i = 1  to  n  do                      // перебираем элементы комбинаторного объекта
   for  j = 1  to  a[i] - 1  do                  // перебираем элементы которые в лексикографическом порядке меньше рассматриваемого
     if элемент j можно поставить на i-e место
       then numOfObject += (коллличество комбинаторных объектов с префиксом от 1 до i-1 равным данному и с i-м элементом равным j)

т.е. он правильно находит номер данного объекта.

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

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

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

 P[n] — количество перестановок размера n
 permutation[n] — данная перестановка
 was[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].

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

Для некоторых комбинаторных объектов, например битовых векторов, можно привести явную биекцию из множества объектов в множество натуральных чисел.В данном случае номером n будет десятичное представление числа, полученное из битового вектора, взятого как двоичное представление числа.Данный алгоритм эффективней общего алгоритма получения номера комбинаторного объекта. Сложность алгоритма [math]O(n)[/math], где n длина битового вектора.

См. также

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