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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Перестановки)
Строка 21: Строка 21:
 
       '''if'''  was[j] = false                              ''// если элемент j ранее не был использован
 
       '''if'''  was[j] = false                              ''// если элемент j ранее не был использован
 
         '''then '''  numOfPermutation += <tex>P_{n-i} </tex>           
 
         '''then '''  numOfPermutation += <tex>P_{n-i} </tex>           
         ''//все перестановки с префиксом длиной i-1 равным нашему, и i-й элемент у которых меньше нашего в лексикографическом порядке идут раньше данной престановки               
+
         ''//все перестановки с префиксом длиной i-1 равным нашему, и i-й элемент у которых меньше  
 +
        ''//нашего в лексикографическом порядке идут раньше данной престановки               
 
         was[i] = true                            // элемент i использован             
 
         was[i] = true                            // элемент i использован             
  

Версия 07:13, 30 октября 2011

Общий алгоритм получения номера в лексикографическом порядке по комбинаторному объекту

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

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

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

Несложно понять, что корректность алгоритма следует из его построения. Сложность алгоритма [math]O(n^{2}f(1..i)) [/math], где [math]f(1..i)[/math] - сложность вычисления количества комбинаторных объектов с данным префиксом. Основную сложность при построении алгоритмов генерации комбинаторных объектов составляет вычисление количества комбинаторных объектов с данным префиксом. Приведем примеры способов нахождения количества некоторых из комбинаторных объектов.

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

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

 [math]P_{n} [/math] — количество перестановок размера 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 += [math]P_{n-i} [/math]          
       //все перестановки с префиксом длиной i-1 равным нашему, и i-й элемент у которых меньше 
       //нашего в лексикографическом порядке идут раньше данной престановки               
       was[i] = true                             // элемент i использован            

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

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

См. также

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

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