Изменения

Перейти к: навигация, поиск

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

363 байта добавлено, 16:36, 12 декабря 2013
Нет описания правки
Следующий алгоритм вычисляет эту сумму
*numOfObject {{---}} искомый номер комбинаторного объекта.
*a[1..n] {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.
*d[i][j] - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)
'''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
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Для битового вектора <tex>k=2</tex>: возможны только 0 и 1. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.
*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
Данный алгоритм работает за <tex>O(n ^ 2) </tex>.
*numOfBitvector {{---}} искомый номер вектора.
*bitvector[1..n] {{---}} данный вектор.
  '''function''' NumOfBitvectorFunc(bitvector: '''Binary''') '''for''' i = 1 '''to''' n '''do''' '''if''' bitvector[i] == 1 numOfBitvector += 2 ** (n - i) '''return''' numOfBitvector
== См. также ==
48
правок

Навигация